[leetcode] 1640. Check Array Formation Through Concatenation

[leetcode] 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 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: trueExplanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]Output: falseExplanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]Output: trueExplanation: 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 <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100The 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).

分析

题目的意思是：给定arr和pieces，检查pieces能够由arr构成，但是pieces[i]的顺序不能变。思路我参考了一下别人的思路，首先pieces中如果包含的数不在arr中，则返回False。然后对pieces根据arr的位置进行排序，然后重新拼接成res，如果和arr相同，则表明是符合要求的，否则不能由arr拆分得到pieces。

代码

class Solution: def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool: for piece in pieces: if(piece[0] not in arr): return False pieces.sort(key=lambda x:arr.index(x[0])) res=[] for piece in pieces: res+=piece if(res==arr): return True else: return False

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。