Sequence Reconstruction Python Solution

lcpy gen -n 444   # by problem number
lcpy gen -s sequence_reconstruction   # by problem name

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]. Since nums is not the only shortest supersequence, we return false.

Input: nums = [1,2,3], sequences = [[1,2]]
Output: false
Explanation: The shortest possible supersequence is [1,2]. Since nums is not the shortest supersequence, we return false.

Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
Output: true
Explanation: The shortest possible supersequence is [1,2,3]. Since nums is the only shortest supersequence, we return true.

class Solution:
    # Time: O(total sequence length)
    # Space: O(n)
    def sequence_reconstruction(self, nums: list[int], sequences: list[list[int]]) -> bool:
        pos = {v: i for i, v in enumerate(nums)}
        following: set[tuple[int, int]] = set()
        for seq in sequences:
            for i in range(len(seq) - 1):
                a, b = seq[i], seq[i + 1]
                if a not in pos or b not in pos or pos[a] >= pos[b]:
                    return False
                following.add((a, b))
        return all((nums[i], nums[i + 1]) in following for i in range(len(nums) - 1))