❓層層篩選 計算有幾個一致的字串 Count the Num of Consistent Strings_#1684

Hümâ H. Yardım on Unsplash

題目敘述 Count the Number of Consistent Strings

給定一個字庫allowed，和一個字串陣列words，請計算有幾個word是一致的?

一致的定義是:

word內所有的英文字母都可以在allowed內找到。

測試範例

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: 
Strings "aaab" and "baa" 是一致的字串。

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: 
全部都是是一致的字串。

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: 
Strings "cc", "acd", "ac", and "d" 是一致的字串。

約束條件

Constraints:

• 1 <= words.length <= 10^4

words陣列長度介於1~一萬之間。

• 1 <= allowed.length <= 26

allowed的長度介於1~26之間。

• 1 <= words[i].length <= 10

每個單字word長度介於1~10之間。

• The characters in allowed are distinct.

allowed內的每個字母都不相同。

• words[i] and allowed contain only lowercase English letters.

題目的輸入只會有小寫英文字母。

演算法 子集合判定

根據題目字串一致的定義和規則，

可以知道，如果word組成字母是allowed的子集合，則word是一致的。

相反的，如果不行，則是不一致的。

掃描每個word，計算有幾個word是一致的即可。

Python程式碼

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        
        allow = set(allowed)

        consistent = 0

        for word in words:
            if set(word).issubset(allow):
                consistent += 1

        return consistent

Go 程式碼

func countConsistentStrings(allowed string, words []string) int {
    
    keyValue := make([]bool, 26)
    for _, v := range allowed {
        keyValue[v - 'a'] = true
    }
    
    count := len(words)
    for _, word := range words {
        for _, wValue := range word {
            if !keyValue[wValue - 'a'] {
                count--
                break
            }
        }
    }
    return count
}

複雜度分析

時間複雜度: O(n)

線性掃描每個單字，總共有O(n)個單字。

空間複雜度: O(1)

需要allowed集合，和word集合，最多為O(26)個英文字母大小=O(1)常數級別。

Reference

[1] Count the Number of Consistent Strings - LeetCode