Sequence Reconstruction

We are given an integer array nums, which is a permutation of integers from 1 to n, and a list of integer sequences. We need to determine if nums is the only shortest supersequence for all the given sequences.

To check if nums is the shortest supersequence, we must verify that every sequence is a subsequence of nums and that no other permutation of nums could be a valid supersequence.

We can solve this by using the following steps:

1. Create an adjacency list: Build a graph where each number in nums has a list of numbers that can come after it based on the given sequences.
2. Check for Validity: Ensure that every sequence in sequences is a valid subsequence of nums. If not, return False.
3. Check for Uniqueness: Use the adjacency list to verify that nums is the only possible supersequence. If there’s an alternative path, return False.

Here’s the code implementing the above steps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        # Step 1: Create an adjacency list
        adj_list = {i: [] for i in nums}
        for seq in sequences:
            for i in range(len(seq) - 1):
                if seq[i] not in adj_list or seq[i + 1] not in adj_list:
                    return False
                adj_list[seq[i]].append(seq[i + 1])

        # Step 2: Check for Validity
        for seq in sequences:
            j = 0
            for i in range(len(nums)):
                if j < len(seq) and nums[i] == seq[j]:
                    j += 1
            if j != len(seq):
                return False

        # Step 3: Check for Uniqueness
        for i in range(len(nums) - 1):
            if nums[i + 1] not in adj_list[nums[i]]:
                return False

        return True

This code checks if nums is the only shortest supersequence for the given sequences by constructing a directed graph and verifying the constraints.