Question

444. 序列重建

English Version

题目描述

给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

• 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
• 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。

_如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。_
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

 

示例 1：

输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：

输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：

输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

 

提示：

• n == nums.length
• 1 <= n <= 104
• nums 是 [1, n] 范围内所有整数的排列
• 1 <= sequences.length <= 104
• 1 <= sequences[i].length <= 104
• 1 <= sum(sequences[i].length) <= 105
• 1 <= sequences[i][j] <= n
• sequences 的所有数组都是 唯一 的
• sequences[i] 是 nums 的一个子序列

解法

方法一：拓扑排序

BFS 实现。

class Solution:
  def sequenceReconstruction(
    self, nums: List[int], sequences: List[List[int]]
  ) -> bool:
    g = defaultdict(list)
    indeg = [0] * len(nums)
    for seq in sequences:
      for a, b in pairwise(seq):
        g[a - 1].append(b - 1)
        indeg[b - 1] += 1
    q = deque(i for i, v in enumerate(indeg) if v == 0)
    while q:
      if len(q) > 1:
        return False
      i = q.popleft()
      for j in g[i]:
        indeg[j] -= 1
        if indeg[j] == 0:
          q.append(j)
    return True

class Solution {
  public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
    int n = nums.length;
    int[] indeg = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var seq : sequences) {
      for (int i = 1; i < seq.size(); ++i) {
        int a = seq.get(i - 1) - 1, b = seq.get(i) - 1;
        g[a].add(b);
        indeg[b]++;
      }
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        q.offer(i);
      }
    }
    while (!q.isEmpty()) {
      if (q.size() > 1) {
        return false;
      }
      int i = q.poll();
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.offer(j);
        }
      }
    }
    return true;
  }
}

class Solution {
public:
  bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
    int n = nums.size();
    vector<vector<int>> g(n);
    vector<int> indeg(n);
    for (auto& seq : sequences) {
      for (int i = 1; i < seq.size(); ++i) {
        int a = seq[i - 1] - 1, b = seq[i] - 1;
        g[a].push_back(b);
        ++indeg[b];
      }
    }
    queue<int> q;
    for (int i = 0; i < n; ++i)
      if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
      if (q.size() > 1) return false;
      int i = q.front();
      q.pop();
      for (int j : g[i])
        if (--indeg[j] == 0) q.push(j);
    }
    return true;
  }
};

func sequenceReconstruction(nums []int, sequences [][]int) bool {
  n := len(nums)
  g := make([][]int, n)
  indeg := make([]int, n)
  for _, seq := range sequences {
    for i := 1; i < len(seq); i++ {
      a, b := seq[i-1]-1, seq[i]-1
      g[a] = append(g[a], b)
      indeg[b]++
    }
  }
  q := []int{}
  for i, v := range indeg {
    if v == 0 {
      q = append(q, i)
    }
  }
  for len(q) > 0 {
    if len(q) > 1 {
      return false
    }
    i := q[0]
    q = q[1:]
    for _, j := range g[i] {
      indeg[j]--
      if indeg[j] == 0 {
        q = append(q, j)
      }
    }
  }
  return true
}