题目描述，难度（简单）

给定一个整数数组 arr ,数组中的每个整数互不相同。
另有一个由整数数组构成的数·组pieces ,其中的整数也互不相同。
请你以任意顺序连接pieces中的数组以形成arr.但是,不允许对每个数组pieces [1]中的整数重新排序。
如果可以连接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
解释:依次连接[911、[4,64]和[78]

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

C++代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

// 算法一：暴力枚举，时间复杂度O(n^2)
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;
    }
};

// 算法二：哈希表，时间复杂度O(n)
class Solution2 
{
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;
    }

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;
    }
};


int main()
{
    Solution solver;
    Solution2 solver2;

    vector<int> arr = {91,4,64,78};
    vector<vector<int>> pieces = {{78}, {4, 64}, {91}};
    cout << solver.canFormArray(arr, pieces) << endl;
    cout << solver2.canFormArray(arr, pieces) << endl;

    arr = {49,18,16};
    pieces = {{16,18,49}};
    cout << solver.canFormArray(arr, pieces) << endl;
    cout << solver2.canFormArray(arr, pieces) << endl;
    return 0;
}