[sword finger offer II 115. reconstruction sequence]

source ： Power button （LeetCode）

describe ：

Given a length of n Array of integers for nums , among nums Is in the range of [1,n] The arrangement of integers . One is also provided 2D An array of integers sequences , among sequences[i] yes nums The subsequence .
Check nums Is it the only shortest Supersequence . The shortest Supersequence yes The shortest length Sequence , And all sequences sequences[i] Are its subsequences . For a given array sequences , There may be multiple valid Supersequence .

• for example , about sequences = [[1,2],[1,3]] , There are two shortest Supersequence ,[1,2,3] and [1,3,2] .

• And for sequences = [[1,2],[1,3],[1,2,3]] , The only possible shortest Supersequence yes [1,2,3] .[1,2,3,4] Is a possible supersequence , But not the shortest .

If nums Is the only shortest sequence Supersequence , Then return to true , Otherwise return to false .
Subsequence One can delete some elements from another sequence or not delete any elements , A sequence that does not change the order of the remaining elements .

Example 1：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3]]
 Output ：false
 explain ： There are two possible supersequences ：[1,2,3] and [1,3,2].
 Sequence  [1,2]  yes [1,2,3] and [1,3,2] The subsequence .
 Sequence  [1,3]  yes [1,2,3] and [1,3,2] The subsequence .
 because  nums  Is not the only shortest supersequence , So back false.

Example 2：

 Input ：nums = [1,2,3], sequences = [[1,2]]
 Output ：false
 explain ： The shortest possible supersequence is  [1,2].
 Sequence  [1,2]  Is its subsequence ：[1,2].
 because  nums  Not the shortest supersequence , So back false.

Example 3：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
 Output ：true
 explain ： The shortest possible supersequence is [1,2,3].
 Sequence  [1,2]  It's a subsequence of it ：[1,2,3].
 Sequence  [1,3]  It's a subsequence of it ：[1,2,3].
 Sequence  [2,3]  It's a subsequence of it ：[1,2,3].
 because  nums  Is the only shortest supersequence , So back true.

Tips ：

• n == nums.length
• 1 <= n <= 10⁴
• nums yes [1, n] The arrangement of all integers in the range
• 1 <= sequences.length <= 10⁴
• 1 <= sequences[i].length <= 10⁴
• 1 <= sum(sequences[i].length) <= 10⁵
• 1 <= sequences[i][j] <= n
• sequences All arrays of are only Of
• sequences[i] yes nums A subsequence of

Method ： A topological sort

Ideas and algorithms

because sequences Each sequence in is nums The subsequence , Therefore, the order of numbers in each sequence is the same as nums The numbers in are in the same order . To judge nums Is it the only shortest supersequence of a sequence , Just judge according to sequences Is the result of constructing a supersequence unique for each sequence in .

Can be sequences All sequences in are treated as directed graphs , Numbers 1 To n Respectively represent n Nodes , There is a directed edge between the nodes represented by adjacent numbers in each sequence . Constructing a supersequence according to a given sequence is equivalent to the topological ordering of a directed graph .

First, calculate the penetration of each node according to the directed edge , Then set all entries to 0 The node of is added to the queue , Topological sort . Every round of topological sorting , The number of elements in the queue represents the number of elements that can be used as the next number of the supersequence , According to the number of elements in the queue , Do the following .

If the number of elements in the queue is greater than 1 , Then the next number of the supersequence is not unique , therefore nums Is not the only shortest supersequence , return false.

If the number of elements in the queue is equal to 1 , Then the next number of the supersequence is the only number in the queue . Take the number out of the queue , Subtract the entry of each number pointed to by this number 1, And turn into 0 The number of is added to the queue .

Repeat the process , Until the number of elements in the queue is not equal to 1 The situation of .

If the number of elements in the queue is greater than 1, be nums Is not the only shortest supersequence , return false.

If the queue is empty , Then the complete topology sorting ends , nums Is the only shortest supersequence , return true.

prove

If in the process of topological sorting , The number of elements in the queue in one round is greater than 1, There are many possibilities for the next number of the supersequence , therefore nums Is not the only shortest supersequence , This is quite intuitive . What needs to be proved is ： When the queue is empty , The complete topology sorting is over , nums Is the only shortest supersequence .

Prove one ： Only when nums When all numbers in appear in at least one sequence , It is possible to perform a complete topology sorting .

because sequences Each sequence in is nums The subsequence , Therefore, there is no ring in the sequence , For all numbers that appear in at least one sequence , There must be a degree of 0 The number of .

If a number does not appear in any sequence , Then the depth of this number is 0, That is, at the beginning, there are multiple numbers of degrees 0, The first number of a supersequence is not unique , It will return in advance false. So if you perform a complete topology sort , be nums All numbers in appear in at least one sequence .

Proof II ： When performing a complete topology sort , The length of the obtained supersequence is n.

Because there is no ring in the sequence , So when the complete topology sorting is finished , All numbers that appear in at least one sequence are in the supersequence . Because performing a complete topological sort means nums All numbers in appear in at least one sequence , therefore nums All the numbers in are in the supersequence , That is, the length of the supersequence is n.

in summary , When the complete topology sorting is finished , nums Is the only shortest supersequence .

Code ：

class Solution {
    
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
    
        int n = nums.size();
        vector<int> indegrees(n + 1);
        vector<unordered_set<int>> graph(n + 1);
        for (auto &sequence : sequences) {
    
            for (int i = 1; i < sequence.size(); i++) {
    
                int prev = sequence[i - 1], next = sequence[i];
                if (!graph[prev].count(next)) {
    
                    graph[prev].emplace(next);
                    indegrees[next]++;
                }
            }
        }
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
    
            if (indegrees[i] == 0) {
    
                qu.emplace(i);
            }
        }
        while (!qu.empty()) {
    
            if (qu.size() > 1) {
    
                return false;
            }
            int num = qu.front();
            qu.pop();
            for (int next : graph[num]) {
    
                indegrees[next]--;
                if (indegrees[next] == 0) {
    
                    qu.emplace(next);
                }
            }
        }
        return true;
    }
};

Execution time ：112 ms, In all C++ Defeated in submission 60.83% Users of
Memory consumption ：71.7 MB, In all C++ Defeated in submission 37.95% Users of
Complexity analysis
Time complexity ： O(n + m), among n It's an array nums The length of , m yes \ sequences The sum of all sequence lengths in . Mapping and topological sorting both need O(n + m) Time for .
Spatial complexity ：O(n + m) , among n It's an array nums The length of , m yes sequences The sum of all sequence lengths in . need O(n + m) Space to store graph information , need O(n) Space to store the penetration of each node , The queue space in the topological sorting process is O(n) .
author：LeetCode-Solution