Leetcode Problem 444. Sequence Reconstruction

444. Sequence Reconstruction

Leetcode Solutions

Topological Sort Approach

  1. Create a graph g and an in-degree map in_degree to represent the directed graph and the number of incoming edges for each node.
  2. Populate g and in_degree by iterating over each sequence in sequences and adding directed edges from each number to the next in the sequence.
  3. Initialize a queue dq and add all nodes with an in-degree of 0 to it.
  4. While dq is not empty, perform the following steps: a. If the length of dq is greater than 1, return False because there is more than one way to continue the topological sort, which means nums is not the only shortest supersequence. b. Pop a node from dq, append it to the result list res, and decrease the in-degree of all its neighbors. c. If any neighbor's in-degree drops to 0, add it to dq.
  5. After the loop, compare res with nums. If they match, return True; otherwise, return False.
UML Thumbnail

Consecutive Pairs Checking Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...