LeetCode 1640. 能否连接形成数组

【LetMeFly】1640.能否连接形成数组

力扣题目链接：https://leetcode.cn/problems/check-array-formation-through-concatenation/

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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扁平化成一维数组，形成数组中的数组所有整数互不相同）

方法一：模拟：遇到一个piece的开始，就得陪伴到这个piece的结束

用一个变量 n o w T h nowTh nowTh来记录当前正在处理pieces的第几个piece。-1表示无处理了一半的piece。

用一个变量 n o w T h T h nowThTh nowThTh来记录当前处理到 p i e c e s [ n o w T h ] pieces[nowTh] pieces[nowTh]的第几个元素。

从前往后遍历arr，如果 n o w T h nowTh nowTh为-1，就说明不是“某个piece处理到了一半”。那么就遍历pieces中所有piece的第一个元素，遇到和arr中当前元素相同的，就更新nowTh，并将nowThTh置为0（该处理pieces[nowTh][0]了）

如果未找到相同元素，就返回false。

之后如果arr中当前遍历到的元素不等于pieces[nowTh][nowThTh]，就返回false

arr成功遍历完后，就返回true

时间复杂度 O ( n × m ) O(n\times m) O(n×m), 其中 n = a r r . l e n g t h , m = p i e c e s . l e n g t h n=arr.length, m = pieces.length n=arr.length,m=pieces.length
空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++

class Solution { public:    bool canFormArray(vector& arr, vector>& pieces) {         int nowTh = -1, nowThTh;        for (int& t : arr) {             if (nowTh == -1) {   // 说明没有哪个piece处理到了一半                for (int i = 0; i < pieces.size(); i++) {   // 那么就找哪个piece的第一个元素和t相同                    if (pieces[i][0] == t) {   // 找到了就更新nowTh和nowThTh                        nowTh = i;                        nowThTh = 0;						break;                    }                }                if (nowTh == -1) {   // 全部遍历完未找到就返回false                    return false;                }            }            if (t != pieces[nowTh][nowThTh]) {   // 这个元素和待处理元素不同就返回false                return false;            }            nowThTh++;  // 下一个待处理元素            if (nowThTh == pieces[nowTh].size()) {   // 这个piece处理完了，下次就需要重新寻找了                nowTh = -1;            }        }        return true;  // 全部成功遍历完了arr    }};