前往
大廳
主題

LeetCode - 1640. Check Array Formation Through Concatenation 解題心得

Not In My Back Yard | 2023-05-17 12:00:05 | 巴幣 100 | 人氣 140

題目連結:


題目意譯:
你被給定一個相異整數陣列 arr 以及一個由整數陣列形成的陣列 pieces,其中 pieces 中的整數彼此相異。你的目標是藉由以任意順序把 pieces 中的陣列串接在一起來形成 arr。不過,你不允許重新排列任何一個陣列 pieces[i] 中的數字。
 
如果可以從 pieces 形成 arr,則回傳真(True);反之,則回傳假(False)。

限制:
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 攤平成一個一維陣列,則所有整數彼此相異)。



範例測資:
範例 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]


解題思維:
由於 pieces 中的數字彼此相異。因此我們現在想要匹配哪個數字 arr[i] 的話,就掃過一次 pieces 來看哪個陣列 pieces[j] 的開頭(即 pieces[j][0])恰好是目標數字。

接著就將該 pieces[j] 剩下的數字與 arr[i] 後續的數字一一匹配。如果中途有衝突的話則代表我們無法把 pieces 重新排列成 arr,因此回傳假。

而如果我們可以把 arr 中所有數字都匹配完成的話,則代表我們找到了一個 pieces 的排列方式來組成 arr。因此回傳真。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作