Very Straightforward C++ Solution by Tracing Digits Order with Detailed Explanation

• This question can be intuitively translated into : "Whether the digit-orders established collectively by all inputs are exactly the same as org ? "
For example: If org == [1,2,3], [[1, 2], [2, 3]] is valid input since it explicitly defines that 2 comes after 1, and 3 comes after 2. Also, there is no extra digit that dose not exist in org.
By contrast, [[1, 2], [1, 3]] is invalid input. Since in org, we record 2 as the parent of 3. However, we cannot infer the same rule from this input --- we can only know "2 comes after 1 and 3 also come after 1" from this input.

``````bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
unordered_map<int, int> orgTree, seqsTree; // Record parent-son relation from back to head
unordered_map<int, int> orgIndex;//Record the correct order of digits in org
for(int i = org.size() - 1; i >= 0; -- i) {
orgTree[org[i]] = org[max(i - 1, 0)];
orgIndex[org[i]] = i;
}
for(vector<int>& vi : seqs) {
if (set<int>(vi.begin(), vi.end()).size() != vi.size()) return false; //Inspect duplicates
for(int i = vi.size() - 1; i >= 0; -- i) {
if (orgTree.find(vi[i]) != orgTree.end() && orgTree.find(vi[max(i - 1, 0)]) != orgTree.end()) {
if (orgIndex[vi[i]] < orgIndex[vi[max(i - 1, 0)]]) return false;//Inspect digit order
if (seqsTree.find(vi[i]) == seqsTree.end() || seqsTree[vi[i]] != orgTree[vi[i]]) seqsTree[vi[i]] = vi[max(i - 1, 0)];
}
else return false;//Either vi[i] or vi[i-1] does not exist in org
}
}
for(unordered_map<int, int>::iterator it = orgTree.begin(); it != orgTree.end(); ++it) {
if (seqsTree.find(it->first) == seqsTree.end() || seqsTree[it->first] != it->second) return false;
}
return true;
}
``````

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