前往
大廳
主題

LeetCode - 2273. Find Resultant Array After Removing Anagrams 解題心得

Not In My Back Yard | 2023-03-27 12:00:21 | 巴幣 1000 | 人氣 155

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的字串陣列 words,其中 words[i] 由小寫英文字母組成。

在一次操作中,選擇任何一個索引值 i 使得 0 < i < words.length 且 words[i - 1] 與 words[i] 互相為易位構詞(Anagram),並將 words[i] 從 words 中刪除。只要你可以選擇滿足這些條件的索引值,持續執行此操作。

回傳執行所有操作後的 words。可以證明在每一次操作以任意順序選擇這些索引值將得到相同的結果。

一個易位構詞為一個字詞或片語以另一個字詞或片語的原始字母重新排列後所形成。例如說,"dacb" 為 "abdc" 的一個易位構詞。

限制:
1 ≦ words.length ≦ 100
1 ≦ words[i].length ≦ 10
words[i] 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: words = ["abba","baba","bbaa","cd","cd"]
輸出: ["abba","cd"]
解釋:
其中一個我們可以得到結果陣列的方式為執行以下操作:
- 由於 words[2] = "bbaa" 和 words[1] = "baba" 是易位構詞,我們選擇索引值 2 並刪除 words[2]。
  現在 words = ["abba","baba","cd","cd"]。
- 由於 words[1] = "baba" 和 words[0] = "abba" 是易位構詞,我們選擇索引值 1 並刪除 words[1]。
  現在 words = ["abba","cd","cd"]。
- 由於 words[2] = "cd" 和 words[1] = "cd" 是易位構詞,我們選擇索引值 2 並刪除 words[2]。
  現在 words = ["abba","cd"]。
現在我們不能執行任何操作,所以 ["abba","cd"] 為最終答案。

範例 2:
輸入: words = ["a","b","c","d","e"]
輸出: ["a","b","c","d","e"]
解釋:
words 中沒有相鄰字串互為易位構詞,所以沒有任何操作被執行。


解題思維:
模擬即可。也就是直接掃過一次 words,只要遇到 words[i] 與 words[i - 1] 是易位構詞就把 words[i] 刪掉即可。

而要判斷是否互為易位構詞,請參見這題




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

創作回應

相關創作

更多創作