Leetcode sequence reconstruction

Leetcode sequence reconstruction

Leetcode: Sequence Reconstruction

June 15, 2018 
Julia likes to prepare the algorithm study for Leetcode seqeuence reconstruction. She already spent 
30 minutes at least to think about the problem first. 

Here is the blog he chosed to use as the source: 
http://www.cnblogs.com/grandyang/p/6032498.html

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. 
The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. 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.

Example 1:

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence 
that can be reconstructed.
Example 2:

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].
Example 3:

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:

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

Output:
true
 
Julia's thinking on June 14, 2018:
org: [1,2,3], seqs: [[1,2],[1,3]]

One thinking:

I think about a few minutes, and I know that it can be solved using graph algorithm, directed graph, 
edges 1 -> 2, 1 -> 3, can we determine the graph from 1 -> 2 -> 3?  It can be a topological sort algorithm. 

I recall indegree, work on indegree nodes first. There is a leetcode code algorithm course schedule II. 

Second thinking:

I also try to think about constraints we have. Maybe we can simplify the algorithm and make time complexity to O(N). 
I am not sure how to simplify the work. I definitely see subproblems and then think about using depth first search, 
solve the problem recursively. 

Analysis from the author of the blog http://www.cnblogs.com/grandyang/p/6032498.html:

这道题给了我们一个序列org，又给我们了一些子序列seqs，问这些子序列能否唯一的重建出原序列。

Two rules are extracted from problem statement:

*** 任意两个数字的顺序必须是一致 ***
能唯一重建的意思就是任意两个数字的顺序必须是一致的，不能说在一个子序列中 1 在 4 的后面，但是在另一个子序列中 1 在 4 的前面，
这样就不是唯一的了。

*** 子序列 seqs 中不能出现其他的数字 ***
还有一点就是，子序列 seqs 中不能出现其他的数字，就是说必须都是原序列中的数字。

*** Propose a solution ***
那么我们可以用了一个一维数组 pos 来记录 org 中每个数字对应的位置，然后用一个 flags 数字来标记当前数字和其前面一个数字是否和 
org 中的顺序一致，用 cnt 来标记还需要验证顺序的数字的个数，初始化 cnt 为 n - 1，因为 n 个数字只需要验证 n - 1 对顺序即可，
然后我们先遍历一遍 org，将每个数字的位置信息存入 pos 中，然后再遍历子序列中的每一个数字，还是要先判断数字是否越界，然后我们
取出当前数字 cur，和其前一位置上的数字 pre，如果在 org 中，pre 在 cur 之后，那么直接返回 false。否则我们看如果 cur 的顺序
没被验证过，而且 pre 是在 cur 的前一个，那么标记 cur 已验证，且 cnt 自减 1，最后如果 cnt 为 0 了，说明所有顺序被成功验证了，
参见代码如下：

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        if (seqs.empty())
        {
          return false;
        }
          
        int n = org.size(), cnt = n - 1;
        
        vector<int> pos(n + 1, 0), flags(n + 1, 0);
        
        bool existed = false;
        
        for (int i = 0; i < n; ++i) pos[org[i]] = i;
        
        for (auto& seq : seqs) {
            for (int i = 0; i < seq.size(); ++i) {
                existed = true;
                
                if (seq[i] <= 0 || seq[i] > n) return false;
                
                if (i == 0) continue;
                
                int pre = seq[i - 1], cur = seq[i];
                
                if (pos[pre] >= pos[cur]) return false;
                
                if (flags[cur] == 0 && pos[pre] + 1 == pos[cur]) 
                {
                    flags[cur] = 1; --cnt;
                }
            }
        }
        
        return cnt == 0 && existed;
    }
};