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

閱讀時間約 1 分鐘

題目敘述 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

83會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
Minimum Bit Flips to Convert Number 給定兩個整數start 和 goal,請問最少需要幾次bit翻轉,使得start等於goal? 註: bit翻轉的定義就是0->1 或者1->0
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
Minimum Bit Flips to Convert Number 給定兩個整數start 和 goal,請問最少需要幾次bit翻轉,使得start等於goal? 註: bit翻轉的定義就是0->1 或者1->0
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
你可能也想看
Google News 追蹤
Thumbnail
🎉週年慶限定優惠,10/24 前加入年訂閱再送 1 個月權限! 本專欄將提供給您最新的市場資訊、產業研究、交易心法、潛力股介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
Thumbnail
🎉週年慶限定優惠,10/24 前加入年訂閱再送 1 個月權限! 本專欄將提供給您最新的市場資訊、產業研究、交易心法、潛力股介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
題目敘述 Distinct Subsequences 給定一個字串s和目標t,請問有多少個s的子序列可以完美匹配目標t ? 也就是說,有多少個s的子序列和目標t相等? 測試範例 Input: s = "rabbbit", t = "rabbit" Output: 3
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試