1640-能否连接形成数组

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

方法一：哈希表

因为数组 arr 每个整数互不相同，且 pieces 的整数也互不相同，所以我们可以通过 arr 固定 pieces 的放置。使用哈希表 index 记录 pieces 各个数组的首元素与数组下标的对应关系。

我们不断地将 pieces 中的数组与数组 arr 相对应，对于当前遍历的元素 arr}[i]，如果它不存在于哈希表中，说明我们无法将 pieces 与数组 arr 相对应，直接返回 false；否则我们找到对应的数组 pieces}[j]，然后将它与 arr}[i] 及之后的整数进行比较（在比较过程中，如果判断相等不成立，直接返回 false），判断都相等后，将 i 相应地向后移。全部 pieces 都匹配成功后，返回 true。

[sol1-Python3]

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        index = {p[0]: i for i, p in enumerate(pieces)}
        i = 0
        while i < len(arr):
            if arr[i] not in index:
                return False
            p = pieces[index[arr[i]]]
            if arr[i: i + len(p)] != p:
                return False
            i += len(p)
        return True

[sol1-C++]

class Solution {
public:
    bool canFormArray(vector<int> &arr, vector<vector<int>> &pieces) {
        unordered_map<int, int> index;
        for (int i = 0; i < pieces.size(); i++) {
            index[pieces[i][0]] = i;
        }
        for (int i = 0; i < arr.size();) {
            auto it = index.find(arr[i]);
            if (it == index.end()) {
                return false;
            }
            for (int x : pieces[it->second]) {
                if (arr[i++] != x) {
                    return false;
                }
            }
        }
        return true;
    }
};

[sol1-Java]

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int n = arr.length, m = pieces.length;
        Map<Integer, Integer> index = new HashMap<Integer, Integer>();
        for (int i = 0; i < m; i++) {
            index.put(pieces[i][0], i);
        }
        for (int i = 0; i < n;) {
            if (!index.containsKey(arr[i])) {
                return false;
            }
            int j = index.get(arr[i]), len = pieces[j].length;
            for (int k = 0; k < len; k++) {
                if (arr[i + k] != pieces[j][k]) {
                    return false;
                }
            }
            i = i + len;
        }
        return true;
    }
}

[sol1-C#]

public class Solution {
    public bool CanFormArray(int[] arr, int[][] pieces) {
        int n = arr.Length, m = pieces.Length;
        Dictionary<int, int> index = new Dictionary<int, int>();
        for (int i = 0; i < m; i++) {
            index.Add(pieces[i][0], i);
        }
        for (int i = 0; i < n;) {
            if (!index.ContainsKey(arr[i])) {
                return false;
            }
            int j = index[arr[i]], len = pieces[j].Length;
            for (int k = 0; k < len; k++) {
                if (arr[i + k] != pieces[j][k]) {
                    return false;
                }
            }
            i = i + len;
        }
        return true;
    }
}

[sol1-C]

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);             
    }
}

bool canFormArray(int* arr, int arrSize, int** pieces, int piecesSize, int* piecesColSize){
    int n = arrSize, m = piecesSize;
    HashItem *index = NULL;
    for (int i = 0; i < m; i++) {
        hashAddItem(&index, pieces[i][0], i);
    }
    for (int i = 0; i < n;) {
        if (!hashFindItem(&index, arr[i])) {
            hashFree(&index);
            return false;
        }
        int j = hashGetItem(&index, arr[i], 0);
        int len = piecesColSize[j];
        for (int k = 0; k < len; k++) {
            if (arr[i + k] != pieces[j][k]) {
                hashFree(&index);
                return false;
            }
        }
        i = i + len;
    }
    hashFree(&index);
    return true;
}

[sol1-JavaScript]

var canFormArray = function(arr, pieces) {
    const n = arr.length, m = pieces.length;
    const index = new Map();
    for (let i = 0; i < m; i++) {
        index.set(pieces[i][0], i);
    }
    for (let i = 0; i < n;) {
        if (!index.has(arr[i])) {
            return false;
        }
        const j = index.get(arr[i]), len = pieces[j].length;
        for (let k = 0; k < len; k++) {
            if (arr[i + k] != pieces[j][k]) {
                return false;
            }
        }
        i = i + len;
    }
    return true;
};

[sol1-Golang]

func canFormArray(arr []int, pieces [][]int) bool {
    index := make(map[int]int, len(pieces))
    for i, p := range pieces {
        index[p[0]] = i
    }
    for i := 0; i < len(arr); {
        j, ok := index[arr[i]]
        if !ok {
            return false
        }
        for _, x := range pieces[j] {
            if arr[i] != x {
                return false
            }
            i++
        }
    }
    return true
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。

• 空间复杂度：O(n)。保存哈希表需要 O(n) 的空间。