LeetCode 1160. Find Words That Can Be Formed by Characters拼寫單詞【Easy】【Python】【字串】
Problem
LeetCode
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.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation:
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation:
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
Note:
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100- All strings contain lowercase English letters only.
問題
力扣
給你一份『詞匯表』（字串陣列） words 和一張『字母表』（字串） chars，
假如你可以用 chars 中的『字母』（字符）拼寫出 words 中的某個『單詞』（字串），那么我們就認為你掌握了這個單詞，
注意：每次拼寫時，chars 中的每個字母都只能用一次，
回傳詞匯表 words 中你掌握的所有單詞的 長度之和，
示例 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，
提示：
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100- 所有字串中都僅包含小寫英文字母
思路
字串
解法一
用 collections，代碼風格比較 pythonic，
Python3代碼
from typing import List
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
# solution one
import collections
res = 0
cnt = collections.Counter(chars)
for word in words:
c = collections.Counter(word)
if all([c[i] <= cnt[i] for i in c]):
res += len(word)
return res
解法二
判斷 word 中各個字符個數是否 <= chars 中這些字符個數，
Python3代碼
from typing import List
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
# solution two
res = 0
for word in words:
n = len(word)
cnt = 0
for i in word:
# word 中字符 i 個數 <= chars 中字符 i 個數
if word.count(i) <= chars.count(i):
cnt += 1
else:
break
# word 可以由 chars 拼出
if cnt == n:
res += cnt
return res
代碼地址
GitHub鏈接
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/175717.html
標籤：Python
上一篇：【2020Python修煉記15】Python語法入門—函式的基本使用
下一篇：談談Python和其他語言的區別