[LeetCode] #1160. Find Words That Can Be Formed by Characters
題目
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
直覺解
構想：
將陣列 words 中的每個元素拿出來，檢查裡面的每個字母是否有在 chars 裡。如果有在 chars 裡，要把 chars 裡相應的字母刪掉，以免重複使用相同的字母。
javascript 實作：
const countCharacters = function(words, chars) {
let sumOfGoodStringLength = 0
words.forEach(word => {
let copyChars = chars
if (word.length > copyChars.length) { return }
for (let i = 0; i < word.length; i++) {
if (copyChars.includes(word[i])) {
copyChars = copyChars.replace(word[i], '')
} else {
return
}
}
sumOfGoodStringLength += word.length
})
return sumOfGoodStringLength
}
效能：
Runtime: 104 ms, faster than 87.15% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 46.2 MB, less than 78.15% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
犯過的低級錯誤：
- 把 return 寫成 continue，結果每個字都變成 good string
- typo
- 把 copyChars = copyChars.replace(word[i], '') 寫成 copyChars.replace(word[i], '')，失去「避免重複使用相同的字母」的效果
直覺解
構想：
用 dictionary 把 chars 中每個字的出現次數存起來。把 word 裡的每個字母跟 dictionary 比對。
python 3 實作：
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
ans = 0
chars_count = {}
for char in chars:
chars_count[char] = (chars_count.get(char) or 0) + 1
for word in words:
copy = chars_count.copy()
for w in word:
result = copy.get(w)
if not result:
break
copy[w] = result - 1
else:
ans += len(word)
return ans
效能：
第一次
Runtime: 136 ms, faster than 71.53% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.9 MB, less than 27.24% of Python3 online submissions for Find Words That Can Be Formed by Characters.
第二次
Runtime: 169 ms, faster than 54.99% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.8 MB, less than 56.87% of Python3 online submissions for Find Words That Can Be Formed by Characters.
第三次
Runtime: 88 ms, faster than 94.03% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 15 MB, less than 6.16% of Python3 online submissions for Find Words That Can Be Formed by Characters.
構想：
參考別人的解後，增加字串長度的檢查。
python 3 實作：
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
ans = 0
chars_count = {}
for char in chars:
chars_count[char] = (chars_count.get(char) or 0) + 1
for word in words:
if len(word) > len(chars):
continue
copy = chars_count.copy()
for w in word:
result = copy.get(w)
if not result:
break
copy[w] = result - 1
else:
ans += len(word)
return ans
效能：
Runtime: 84 ms, faster than 96.63% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.8 MB, less than 27.24% of Python3 online submissions for Find Words That Can Be Formed by Characters.
其他：
比 chars_count[char] = (chars_count.get(char) or 0) + 1 更好的寫法： chars_count[char] = chars_count.get(char, 0) + 1
參考資料：讓你的 Python 程式碼優雅又地道 §用字典計數
研究別人的解
來源：sample 68 ms submission
python 3 實作：
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
ans = 0
for word in words:
for ch in word:
if word.count(ch) > chars.count(ch):
break
else:
ans += len(word)
return ans
效能：
第一次
Runtime: 117 ms, faster than 75.16% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.8 MB, less than 27.24% of Python3 online submissions for Find Words That Can Be Formed by Characters.
第二次
Runtime: 76 ms, faster than 99.42% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.7 MB, less than 79.96% of Python3 online submissions for Find Words That Can Be Formed by Characters.
研究感想：
用 python 內建的函式，Python String count() Method。
研究別人的解
來源：Alpha Camp LeetCode 訓練營講師 Wesley 介紹的其中一個解
python 3 實作：
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
s = 0
for word in words:
valid = True
chars_copy = list(chars)
for w in word:
if w not in chars_copy:
valid = False
break
else:
chars_copy.remove(w)
if valid:
s += len(word)
return s
效能：
第一次
Runtime: 323 ms, faster than 15.11% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.8 MB, less than 56.87% of Python3 online submissions for Find Words That Can Be Formed by Characters.
第二次
Runtime: 308 ms, faster than 17.70% of Python3 online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 14.9 MB, less than 27.24% of Python3 online submissions for Find Words That Can Be Formed by Characters.
研究感想：
用 python 的 list。
研究別人的解
來源：Alpha Camp LeetCode 訓練營講師 Wesley 介紹的其中一個解
javascript 實作：
/**
* create array with zeros : Array(26).fill(0);
* chars.charCodeAt(i) - 97
* console.log(word);
* words.forEach(word => {});
*/
var countCharacters = function(words, chars) {
var ans = 0;
var charsCount = Array(26).fill(0);
for (var i = 0; i < chars.length; i++) {
var index = chars.charCodeAt(i) - 97;
charsCount[index] += 1;
}
words.forEach(word => {
seen = Array(26).fill(0);
for ( var i = 0; i<word.length; i++ ) {
var index = word.charCodeAt(i) - 97;
seen[index] += 1;
}
var valid = true;
for (var i = 0; i < 26; i++){
if(charsCount[i] < seen[i]){
valid = false;
break;
}
}
if(valid){
ans += word.length;
}
});
return ans;
};
效能：
第一次
Runtime: 173 ms, faster than 58.90% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 45.1 MB, less than 97.95% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
第二次
Runtime: 96 ms, faster than 93.15% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 45 MB, less than 97.95% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
研究感想：
不用 hash map，改成用 array 記錄符號出現次數，array 的 index 對應到符號的編碼。
最後更新日期： 2021 年 8 月 31 日
Comments
Post a Comment