444 Sequence Reconstruction

444. Sequence Reconstruction

1. Question

Check whether the original sequenceorgcan be uniquely reconstructed from the sequences inseqs. Theorgsequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences inseqs(i.e., a shortest sequence so that all sequences inseqsare subsequences of it). Determine whether there is only one sequence that can be reconstructed fromseqsand it is theorgsequence.

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

2. Implementation

(1) BFS

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> adjList = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();

        for (List<Integer> seq : seqs) {
            for (int num : seq) {
                adjList.putIfAbsent(num, new HashSet<>());
                inDegree.putIfAbsent(num, 0);
            }
        }

        for (List<Integer> seq : seqs) {
            for (int i = 0; i < seq.size() - 1; i++) {
                if (adjList.get(seq.get(i)).add(seq.get(i + 1))) {
                    inDegree.put(seq.get(i + 1), inDegree.get(seq.get(i + 1)) + 1);
                }
            }
        }

        // org can not be constructed from seqs because some number don't exist in org or sequences
        if (org.length != inDegree.size()) {
            return false;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int num : inDegree.keySet()) {
            if (inDegree.get(num) == 0) {
                queue.add(num);
            }
        }

        int count = 0;

        while (!queue.isEmpty()) {
            // Cannot uniquely construct sequence
            if (queue.size() > 1) {
                return false;
            }

            int curNum = queue.remove();
            ++count;

            for (int nextNum : adjList.get(curNum)) {
                inDegree.put(nextNum, inDegree.get(nextNum) - 1);
                if (inDegree.get(nextNum) == 0) {
                    queue.add(nextNum);
                }
            }
        }
        return count == org.length;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(m)， m为seq中unique的数字个数，空间复杂度O(m)