1160. Find Words That Can Be Formed by Characters (Easy)

Question

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

1
2
3
4

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

1
2
3
4

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. 1 <= words.length <= 1000
2. 1 <= words[i].length, chars.length <= 100
3. All strings contain lowercase English letters only.

分析/解題

給定字串陣列words和一個字串chars，
如果陣列中的一個字串能被定義為good，
代表它是能由chars的中的字元組成(每個字元最多只能使用一次 )，
試將所有good的字串長度加總回傳。

一般用來描述某個項目儲存多少值都會使用HashTable/HashMap，
對應到Python則通常可使用dictionary。
HashTable相關的儲存方式有搜尋為O(1) 的特性，
和一般常見的搜尋資料結構如Binary Search Tree需要O(log N) 不同，
原因是因為會實作hash function，令不同的值儲存的時候能夠得到不同的hash值，從而直接找到對應的位置。
(但當hash function的選擇不好 ，或儲存的東西太多時，
有機會發生碰撞(collision) 問題，導致查找時間加長，這裡暫不討論。)

在題目的條件限定在英文字母相關的時候或有特定長度限制時，
我們常可以用很簡單的方式來進行hash table/hash map的操作，
例如英文字母a~z只有26個，
如果題目和計算字母出現的次數有關聯性的話，
我們可以直接以一個長度為26的陣列/串列來記錄 。

以這題來說，題目所要求的檢查方式，
就是先確認chars裡面有幾個a, 幾個b, …… , 幾個z ，
接下來對每個字串 確認其組成，
一旦組成需要的個數大於chars所擁有的，我們就可以直接跳過它 ；
反之若每個字母所需的個數都滿足，
則將要回傳的結果加上這個字串的長度，
一直到全數檢查完畢即可回傳結果。

下面Java的程式碼部分演示了上面所提到的步驟。
裡面用到語法蜜糖(Syntactic sugar)的作法，讀者應稍加掌握，
如for迴圈Java有提供連續從array中依序取出單個變數的寫法，
類似於Python中**”for word in words”** 的方式。
我們將check的部分獨立出來，作為檢查並回傳長度的部分，
一旦沒有成立，直接回傳0，若最終檢查通過則將len(word)回傳。

之前應該也提到過char可以使用ASCII的代表數字來加減 ，
所以這邊取a到z來做為index 0到26，起始的基準點是’a’。

Java

Python的部分，使用Counter 可以很簡便的計算一個字串中的字母組成，
我們可以直接檢查每個key的值的大小來確認是否足夠組成，
但需留意Counter並不會 放置沒有出現的字母的key，
故每次要先檢查是否dic中本來就沒有現在要檢查的key值，
避免發生錯誤。

更簡便的方式是直接使用count 來計算某個字母在字串裡面出現的次數。
這個應該是目前Python答案中跑最快的方法，
但可能是因為測試資料中比較常出現False的狀況，
導致word不用每個字母都算完就結束了 。
不然在最糟的狀況下，word的每個字母應該都會算一次count，
且相同的字母在不同的位置上還會重新再算過一次；
雖然時間複雜度還是一樣(字串最長限定是100)，
若整份資料比較容易是good的字居多的話，
並不建議用這樣子的方式操作。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(Java: O(N)/O(1)，
準確來說，最大要走完所有字的長度(所以應該可以說N個字*長度L)，
空間的部分，使用了26個字母來做為查表用的分類，
所以同一時間用到的只會有2組長度26的陣列及幾個暫存用變數
Python: 對二個解也都是 O(N)/O(1)，
但第二個解在最差的狀況下會每個字母都重覆掃過。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~