- Sequence Reconstruction
中等
https://leetcode-cn.com/problems/sequence-reconstruction/
You are given an integer array nums of length n where nums is a permutation of the integers in the range [1, n]. You are also given a 2D integer array sequences where sequences[i] is a subsequence of nums.
Check if nums is the shortest possible and the only supersequence. The shortest supersequence is a sequence with the shortest length and has all sequences[i] as subsequences. There could be multiple valid supersequences for the given array sequences.
- For example, for sequences = [[1,2],[1,3]], there are two shortest supersequences, [1,2,3] and [1,3,2].
- While for sequences = [[1,2],[1,3],[1,2,3]], the only shortest supersequence possible is [1,2,3]. [1,2,3,4] is a possible supersequence but not the shortest.
Return true if nums is the only shortest supersequence for sequences, or false otherwise.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,2,3], sequences = [[1,2],[1,3]]
Output: false
Explanation: There are two possible supersequences: [1,2,3] and [1,3,2].
The sequence [1,2] is a subsequence of both: [1,2,3] and [1,3,2].
The sequence [1,3] is a subsequence of both: [1,2,3] and [1,3,2].
Since nums is not the only shortest supersequence, we return false.
Example 2:
Input: nums = [1,2,3], sequences = [[1,2]]
Output: false
Explanation: The shortest possible supersequence is [1,2].
The sequence [1,2] is a subsequence of it: [1,2].
Since nums is not the shortest supersequence, we return false.
Example 3:
Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
Output: true
Explanation: The shortest possible supersequence is [1,2,3].
The sequence [1,2] is a subsequence of it: [1,2,3].
The sequence [1,3] is a subsequence of it: [1,2,3].
The sequence [2,3] is a subsequence of it: [1,2,3].
Since nums is the only shortest supersequence, we return true.
Constraints:
n == nums.length
1 <= n <= 104
nums is a permutation of all the integers in the range [1, n].
1 <= sequences.length <= 104
1 <= sequences[i].length <= 104
1 <= sum(sequences[i].length) <= 105
1 <= sequences[i][j] <= n
All the arrays of sequences are unique.
sequences[i] is a subsequence of nums.
相关企业
- 谷歌 Google|2
相关标签
- Graph
- Topological Sort
- Array
相似题目
- Course Schedule II 中等
class Solution:
def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
node2NextNodesGraph, node2indegreeMap = self.buildGraphAndIndegreeMap(sequences)
print(node2NextNodesGraph, node2indegreeMap )
# bfs to build topo order which is supersequeue
startnodes = [node for node in node2indegreeMap if node2indegreeMap[node] == 0]
queue = collections.deque(startnodes)
topoorder = []
while queue:
if len(queue) > 1: # every step should have one 1 choose otherwise there is more than one shortest supersequeue
return False
curr_node = queue.popleft() # if only one shortest supersequence then here there is only one option
topoorder.append(curr_node)
for next_node in node2NextNodesGraph[curr_node]:
node2indegreeMap[next_node] -= 1
if node2indegreeMap[next_node] == 0:
queue.append(next_node)
print(topoorder)
if len(topoorder) == len(node2NextNodesGraph):
if topoorder == nums:
return True
return False
def buildGraphAndIndegreeMap(self, sequences):
node2NextNodesGraph = dict()
node2indegreeMap = dict()
for seq in sequences:
for node in seq:
if node not in node2NextNodesGraph:
node2NextNodesGraph[node] = set()
node2indegreeMap[node] = 0
for seq in sequences:
for i in range(1, len(seq)):
node2NextNodesGraph[seq[i-1]].add(seq[i])
for node in node2NextNodesGraph:
for next_node in node2NextNodesGraph[node]:
node2indegreeMap[next_node] += 1
return node2NextNodesGraph, node2indegreeMap