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).
Solution: Hashtable
Store the index of the first number of each piece, for each number a in arr, concat the entire piece array whose first element equals to a.
Time complexity: O(n)
Space complexity: O(n)
C++
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) { unordered_map<int, int> m; for (int i = 0; i < pieces.size(); ++i) m[pieces[i][0]] = i; vector<int> ans; for (int a : arr) { if (!m.count(a)) continue; ans.insert(end(ans), begin(pieces[m[a]]), end(pieces[m[a]])); } return ans == arr; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment