Understanding the problem


  • 4

    EXAMPLE 1
    seqs = [[1,2], [1,3]]

    Question: Using seqs, what are the shortest common supersequences we can make?
    Answer: [1,2,3] and [1 3 2].

    Explanation:

    • [1,2,3] is valid, since every sequence in seqs is a subsequence of [1,2,3]
    [1,2,3]    [1,2,3]
     * *        *   *
    
    • [1,3,2] is valid since every sequence in seqs is a subsequence of [1,3,2]
    [1,3,2]    [1,3,2]
     *   *      * *
    

    Solution: False - there are multiple such supersequences.


    EXAMPLE 3
    seqs = [[1,2],[1,3],[2,3]]

    Question: Using seqs, what are the shortest common supersequences we can make?
    Answer: [1,2,3]

    Explanation:

    • [1,2,3] is valid since every sequence in seqs is a subsequence of [1,2,3]
    [1,2,3]    [1,2,3]    [1,2,3]
     * *        *   *        * *
    

    Solution: True - solution is unique and equal to target [1,2,3].


  • 1
    T

    what about Example 4?

    Input:
    org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

    Output:
    true


  • 0
    S

    what about [[1,2],[1,3],[2,3],[3,3]], [1,2,3,3], is this valid? I think it is, but return False.


  • 0
    S

    What about -

    [1]
    [[1,1]]
    

    Why is this false? problem is very unclear or convoluted

    Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

    Does this mean cycle in graph or sequence that matters - results in FALSE?


  • 1
    X

    @samuelma
    Because [[1,2],[1,3],[2,3],[3,3]] can also construct [1,3,2,3], so the sequences that seqs can construct is not unique.


  • 0
    X

    @sha256pki
    Although [1] is subsequence of [1,1], a single 1 can not construct [1,1]


  • 0
    I

    @Xing_ What about [6,2,1, 5,2] for [[6,2,1], [2, 1, 5, 2]] shouldn't it be a "true"? While the solution ouputs "false"


Log in to reply
 

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