ETH官方钱包

前往
大廳
主題

LeetCode - 890. Find and Replace Pattern 解題心得

Not In My Back Yard | 2021-06-28 00:00:01 | 巴幣 0 | 人氣 199

題目連結:


題目意譯:
給定一個字串列表 words 以及一字串 pattern,回傳 words[i] 的一個列表其中的每個字詞皆符合模式(即 pattern)。你可以任意順序回傳答案。

一個字詞符合模式,如果存在一個字母排列 p 滿足將 pattern 中每個字母 x 替換為 p(x) ,我們便會得到該字詞。

記得,一個字母排列為字母與字母間的一個對射(Bijection):每個字母映射到其他的字母,且沒有字母映射到同一個字母。

限制:
1 ≦ pattern.length ≦ 20
1 ≦ words.length ≦ 50
words[i].length == pattern.length
pattern 和 words[i] 為小寫英文字母。



範例測資:
範例 1:
輸入: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
輸出: ["mee","aqq"]
解釋: "mee" 符合給定的模式,因為其有著排列 {a → m, b → e, ……} 。
"ccc" 不符合模式因為 {a → c, b → c, ……} 不是一個排列,因其 a 以及 b 同時映射到同一個字母。

範例 2:
輸入: words = ["a","b","c"], pattern = "a"
輸出: ["a","b","c"]


解題思維:
掃過 words 中的每個字詞。當 words[i] 符合模式時,代表 words[i] 與 pattern 同構,如這題作法便可以判斷兩個字串是否同構。

將所有與 pattern 同構的字串放進答案陣列裡即是所求。




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

創作回應

更多創作