There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.
Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.
Example 1:
Input: text = "hello world", brokenLetters = "ad" Output: 1 Explanation: We cannot type "world" because the 'd' key is broken.
Example 2:
Input: text = "leet code", brokenLetters = "lt" Output: 1 Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.
Example 3:
Input: text = "leet code", brokenLetters = "e" Output: 0 Explanation: We cannot type either word because the 'e' key is broken.
Constraints:
1 <= text.length <= 1040 <= brokenLetters.length <= 26textconsists of words separated by a single space without any leading or trailing spaces.- Each word only consists of lowercase English letters.
brokenLettersconsists of distinct lowercase English letters.
Solution: Hashset / bitset
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int canBeTypedWords(string text, string brokenLetters) { const int n = text.size(); bitset<26> b; for (char c : brokenLetters) b.set(c - 'a'); int ans = 0; for (int i = 0, broken = 0; i <= n; ++i) { if (i == n || text[i] == ' ') { if (!broken) ++ans; broken = 0; } else { broken |= b[text[i] - 'a']; } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment