主題

LeetCode - 1160. Find Words That Can Be Formed by Characters 解題心得

Not In My Back Yard | 2021-03-30 00:00:07 | 巴幣 0 | 人氣 60

題目連結:


題目意譯:
你被給定一個字串陣列 words 以及一個字串 chars。

一個字串是好的,如果其可以被 chars 中的字元所組成(每個字元只能使用一次)。

回傳所有 words 中的好字串之長度總和。

注:
1 ≦ words.length ≦ 1000
1 ≦ words[i].length 、 chars.length ≦ 100
所有字串只包含小寫英文字母。



範例測資:
範例 1:
輸入: words = ["cat","bt","hat","tree"], chars = "atach"
輸出: 6
解釋: 可以組成之字串為 "cat" 和 "hat",所以答案為 3 + 3 = 6。


範例 2:
輸入: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
輸出: 10
解釋: 可以組成之字串為 "hello" 和 "world",所以答案為 5 + 5 = 10。


解題思維:
先用一個陣列 C1 去統計 chars 中每種字元的出現次數。再用另一個陣列 C2 去統計每個字串 words[i] 的字母出現次數(每統計完一個字串要統計下一個時記得將計數歸零)。

接著掃過所有的字元種類 c,如果 C1[c] 有任何時刻小於 C2[c],則代表著目前判斷的字串 words[i] 無法被 chars 所組成(因為 words[i] 有某字元的出現次數比 chars 中的多)。

然後將那些沒有發生過 C1[c] < C2[c] 的所有字串之長度加總即是所求。




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

創作回應

更多創作