Teaching Kids Programming: Videos on Data Structures and Algorithms
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.text consists of words separated by a single space without any leading or trailing spaces.
Each word only consists of lowercase English letters.
brokenLetters consists of distinct lowercase English letters.Hints:
Check each word separately if it can be typed.
A word can be typed if all its letters are not broken.
Maximum Number of Words You Can Type
By using hash table (set) we can achieve O(1) lookup to see if a character is broken (in the list). Then, we split the sentence by whitespaces and then go through each character in each word and increment the answer if all characters in that word contain non of the broken list.
1 2 3 4 5 6 7 8 | class Solution: def canBeTypedWords(self, text: str, brokenLetters: str) -> int: b = set(brokenLetters) ans = 0 for i in text.split(' '): if all(j not in b for j in i): ans += 1 return ans |
class Solution: def canBeTypedWords(self, text: str, brokenLetters: str) -> int: b = set(brokenLetters) ans = 0 for i in text.split(' '): if all(j not in b for j in i): ans += 1 return ans
Time complexity is O(N) where N is the number of the characters in the sentence. The space complexity is O(M) where M is the number of broken characters.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C Program to Perform ROT47 Cipher
Next Post: C Program to Time Command using clock_gettime