Python: Detailed & easy to understand solution


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/72895/python-detailed-easy-to-understand-solution

    Sequence Reconstruction https://leetcode.com/problems/sequence-reconstruction/

    Verify Unique Topological Sort Order

    **What does a super sequence really mean? **

    • It means a topological sort of input graph. Therefore every sequence (within the sequences) will be a subsequences of org. How will you check this condition? Every edge (u,v) in sequence will honor this precedence in org i.e. index_position(u) < index_position(v)
    • For a sequence [5,2,3,6], it is enough to test the edges [5,2], [2,3], and [3,6]. This automatically implies [5,3] and [2,6].

    **What is meant by the super sequence being unique? **

    • In other words, when will the topological sort be unique? If and only if every consecutive items in org are edges then we have a unique sequence. Use an example: [1,2] and [1,3] will give us two valid super-sequences: [1,2,3] or [1,3,2]. There is no unique sequence since there is no precendence defined for nodes 2 and 3. Here is a wikipedia article about this: https://en.wikipedia.org/wiki/Topological_sorting#Uniqueness

    Key Examples to Consider

    • Empty sequence is an error
      [1]
      []

    • Any sequence item not in org is an Error
      [5,3,2,4,1]
      [[5,3,2,4],[4,1],[1],[3],[2,4],[1,1000000000]]

    [5,3,2,4,1]
    [[5,3,2,4],[4,1],[1],[3],[2,4], [1000000000]]

    • Self direction or a cycle is an error. Hence: pos[seq[i]] >= pos[seq[i+1]]
      [1]
      [[1,1]]

    • Make sure all orig items are marked
      [1]
      [[],[]]

    Code

    class Solution(object):
        def sequenceReconstruction(self, org, seqs):
            """
            :type org: List[int]
            :type seqs: List[List[int]]
            :rtype: bool
            """
            if not seqs:
                return False
            pos, marked, orig_marked = {x:idx for idx,x in enumerate(org)}, set([]), set([])
            for seq in seqs:
                for i in range(len(seq)):
                    if seq[i] in pos:
                        orig_marked.add(pos[seq[i]])
                    if seq[i] not in pos:
                        return False
                    elif i+1 < len(seq) and (seq[i+1] not in pos or pos[seq[i]] >= pos[seq[i+1]]):
                        return False
                    elif i+1 < len(seq) and (pos[seq[i]]+1 == pos[seq[i+1]]):
                        marked.add((pos[seq[i]], pos[seq[i+1]]))
            return (len(marked) == len(org)-1) and len(orig_marked) == len(org)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.