1640. Check Array Formation Through Concatenation
Description
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 arrayarr
frompieces
. Otherwise, return false
.
Example 1:
Example 2:
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).
Tags
Array, Hash Table, Sort
Solution
Employ a hash table to index pieces using the first character of each piece as the key to speedup lookup. Then, we use each character in arr
to query a piece and join them together to obtain a new array. Return the result that if arr
and the new array are the same.
Complexity
Time complexity: ,
n
for the length ofarr
;Space complexity: ,
m
for the length ofpieces
.
Code
Reference
Last updated
Was this helpful?