Question

1764. Form Array by Concatenating Subarrays of Another Array

中文文档

Description

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the ith subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)th subarray appears before the ith subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true _if you can do this task, and_ false _otherwise_.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

 

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

 

Constraints:

• groups.length == n
• 1 <= n <= 103
• 1 <= groups[i].length, sum(groups[i].length) <= 103
• 1 <= nums.length <= 103
• -107 <= groups[i][j], nums[k] <= 107

Solutions

Solution 1

class Solution:
  def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
    n, m = len(groups), len(nums)
    i = j = 0
    while i < n and j < m:
      g = groups[i]
      if g == nums[j : j + len(g)]:
        j += len(g)
        i += 1
      else:
        j += 1
    return i == n

class Solution {
  public boolean canChoose(int[][] groups, int[] nums) {
    int n = groups.length, m = nums.length;
    int i = 0;
    for (int j = 0; i < n && j < m;) {
      if (check(groups[i], nums, j)) {
        j += groups[i].length;
        ++i;
      } else {
        ++j;
      }
    }
    return i == n;
  }

  private boolean check(int[] a, int[] b, int j) {
    int m = a.length, n = b.length;
    int i = 0;
    for (; i < m && j < n; ++i, ++j) {
      if (a[i] != b[j]) {
        return false;
      }
    }
    return i == m;
  }
}

class Solution {
public:
  bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
    auto check = [&](vector<int>& a, vector<int>& b, int j) {
      int m = a.size(), n = b.size();
      int i = 0;
      for (; i < m && j < n; ++i, ++j) {
        if (a[i] != b[j]) {
          return false;
        }
      }
      return i == m;
    };
    int n = groups.size(), m = nums.size();
    int i = 0;
    for (int j = 0; i < n && j < m;) {
      if (check(groups[i], nums, j)) {
        j += groups[i].size();
        ++i;
      } else {
        ++j;
      }
    }
    return i == n;
  }
};

func canChoose(groups [][]int, nums []int) bool {
  check := func(a, b []int, j int) bool {
    m, n := len(a), len(b)
    i := 0
    for ; i < m && j < n; i, j = i+1, j+1 {
      if a[i] != b[j] {
        return false
      }
    }
    return i == m
  }
  n, m := len(groups), len(nums)
  i := 0
  for j := 0; i < n && j < m; {
    if check(groups[i], nums, j) {
      j += len(groups[i])
      i++
    } else {
      j++
    }
  }
  return i == n
}