题目描述

给定一个整数数组 arr，数组中的每个整数 互不相同。另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同。请你以 任意顺序 连接 pieces 中的数组以形成 arr。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。

如果可以连接 pieces 中的数组形成 arr，返回 true；否则，返回 false。

样例

输入：arr = [85], pieces = [[85]]
输出：true

输入：arr = [15,88], pieces = [[88],[15]]
输出：true
解释：依次连接 [15] 和 [88]

输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]

输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出：true
解释：依次连接 [91]、[4,64] 和 [78]

输入：arr = [1,3,5,7], pieces = [[2,4,6,8]]
输出：false

限制

• 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
• arr 中的整数 互不相同。
• pieces 中的整数 互不相同（也就是说，如果将 pieces 扁平化成一维数组，数组中的所有整数互不相同）

算法1

(暴力枚举) $O(n^2)$

1. 对于 arr 中的每个数字，暴力在 pieces 中寻找是否有子数组，满足其第一项等于这个数字。
2. 如果没有，返回 false；如果有，则依次检查子数组之后的数字。

时间复杂度

• 最坏情况下，每个数字都需要遍历所有的子数组，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    bool isEqual(int st, const vector<int> &arr, const vector<int> &v) {
        for (int i = st, j = 0; j < v.size(); i++, j++)
            if (arr[i] != v[j])
                return false;
        return true;
    }

    int find(int st, const vector<int>& arr, const vector<vector<int>> &pieces) {
        for (const auto &v : pieces)
            if (isEqual(st, arr, v))
                return v.size();
        return -1;
    }

public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        const int n = arr.size();
        int i = 0;
        while (i < n) {
            int len = find(i, arr, pieces);
            if (len == -1) return false;
            i += len;
        }
        return true;
    }
};

算法2

(哈希表) $O(n)$

1. 用哈希表记录每个子数组开头数字所对应的数组。
2. 对于 arr 中的每个数字，在哈希表中查找这个数字。
3. 如果不存在，返回 false。如果存在，则依次检查子数组之后的数字。

时间复杂度

• 预处理哈希表的时间复杂度为 $O(n)$。
• 检查时，每个数字最多被遍历一次。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
private:
    bool isEqual(int st, const vector<int> &arr, vector<int> &v) {
        for (int i = st, j = 0; j < v.size(); i++, j++)
            if (arr[i] != v[j])
                return false;
        return true;
    }

public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, vector<int>> seen;
        for (const auto &v : pieces)
            seen[v[0]] = v;

        const int n = arr.size();
        int i = 0;
        while (i < n) {
            if (seen.find(arr[i]) == seen.end())
                return false;
            if (!isEqual(i, arr, seen[arr[i]]))
                return false;
            i += seen[arr[i]].size();
        }
        return true;
    }
};