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


  • 0
    A

    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;
    }
    

Log in to reply
 

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