Description
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 <= 26text 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.
Solutions
Solution 1: Array or Hash Table
We can use a hash table or an array s of length 26 to record all the broken letter keys.
Then, we traverse each word w in the string text, and if any letter c in w appears in s, it means that the word cannot be typed, and we do not need to add one to the answer. Otherwise, we need to add one to the answer.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(|Σ|), where n is the length of the string text, and |Σ| is the size of the alphabet. In this problem, |Σ|=26.
PythonJavaC++GoTypeScriptRustC#
class Solution:
def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
s = set(brokenLetters)
return sum(all(c not in s for c in w) for w in text.split())(code-box)
class Solution {
public int canBeTypedWords(String text, String brokenLetters) {
boolean[] s = new boolean[26];
for (char c : brokenLetters.toCharArray()) {
s[c - 'a'] = true;
}
int ans = 0;
for (String w : text.split(" ")) {
for (char c : w.toCharArray()) {
if (s[c - 'a']) {
--ans;
break;
}
}
++ans;
}
return ans;
}
}(code-box)
class Solution {
public:
int canBeTypedWords(string text, string brokenLetters) {
bool s[26]{};
for (char c : brokenLetters) {
s[c - 'a'] = true;
}
int ans = 0;
stringstream ss(text);
string w;
while (ss >> w) {
for (char c : w) {
if (s[c - 'a']) {
--ans;
break;
}
}
++ans;
}
return ans;
}
};(code-box)
func canBeTypedWords(text string, brokenLetters string) (ans int) {
s := [26]bool{}
for _, c := range brokenLetters {
s[c-'a'] = true
}
for _, w := range strings.Split(text, " ") {
for _, c := range w {
if s[c-'a'] {
ans--
break
}
}
ans++
}
return
}(code-box)
function canBeTypedWords(text: string, brokenLetters: string): number {
const s: boolean[] = Array(26).fill(false);
for (const c of brokenLetters) {
s[c.charCodeAt(0) - 'a'.charCodeAt(0)] = true;
}
let ans = 0;
for (const w of text.split(' ')) {
for (const c of w) {
if (s[c.charCodeAt(0) - 'a'.charCodeAt(0)]) {
--ans;
break;
}
}
++ans;
}
return ans;
}(code-box)
impl Solution {
pub fn can_be_typed_words(text: String, broken_letters: String) -> i32 {
let mut s = vec![false; 26];
for c in broken_letters.chars() {
s[(c as usize) - ('a' as usize)] = true;
}
let mut ans = 0;
let words = text.split_whitespace();
for w in words {
for c in w.chars() {
if s[(c as usize) - ('a' as usize)] {
ans -= 1;
break;
}
}
ans += 1;
}
ans
}
}(code-box)
public class Solution {
public int CanBeTypedWords(string text, string brokenLetters) {
bool[] s = new bool[26];
foreach (char c in brokenLetters) {
s[c - 'a'] = true;
}
int ans = 0;
string[] words = text.Split(' ');
foreach (string w in words) {
foreach (char c in w) {
if (s[c - 'a']) {
--ans;
break;
}
}
++ans;
}
return ans;
}
}(code-box)
