0%

LeetCode 1640. Check Array Formation Through Concatenation

Posted on Edited on In

题目

原题在此
You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].
Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

  • 1 <= pieces.length <= arr.length <= 100
  • sum(pieces[i].length) == arr.length
  • 1 <= pieces[i].length <= arr.length
  • 1 <= arr[i], pieces[i][j] <= 100
  • The integers in arr are distinct.
  • The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

分析

版本一

这一版的思路很单纯,把pieces中的每个piece以piece[0]为key存入map中以便随机访问,再无脑按照arr中出现的顺序拼起来.最后看看拼起来的和arr是否相等.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, vector<int>> mp;
        vector<int> attached;
        for(vector<int> p : pieces) mp[p[0]] = p;
        for(int i : arr)
            if (mp.find(i) != mp.end())
                attached.insert(attached.end(), mp[i].begin(), mp[i].end());
        return attached == arr;
    }
};

改进思路

  1. Map中没必要存整个piece数组,存piece[0]就可以.
  2. 根据题目Constraints部分的描述,外加数组元素是distinct的,可以用数组替代Map.
  3. 在遍历arr的过程中,每次必须找到一个piece以arr[i]开头,且整段piece和arr的局部必须完全一致,否则即可返回false.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        // mp<"first number of a piece", "index of this piece in pieces">
        vector<int> mp(101, -1);
        for(int i = 0; i < pieces.size(); ++i) mp[pieces[i][0]] = i;
        for(int i = 0; i < arr.size();) {
            int pindex = mp[arr[i]];
            if(pindex == -1) return false; // no piece start with this number;
            int j = 0;
            while(j < pieces[pindex].size())
                if(arr[i++] != pieces[pindex][j++]) return false;
        }
        return true;
    }
};