Question

1935. Maximum Number of Words You Can Type

中文文档

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 <= 104
• 0 <= brokenLetters.length <= 26
• 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.

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(|\Sigma|)$, where $n$ is the length of the string $text$, and $|\Sigma|$ is the size of the alphabet. In this problem, $|\Sigma|=26$.

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())

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;
  }
}

class Solution {
public:
  int canBeTypedWords(string text, string brokenLetters) {
    bool s[26]{};
    for (char& c : brokenLetters) {
      s[c - 'a'] = true;
    }
    int ans = 0;
    for (auto& w : split(text, ' ')) {
      for (char& c : w) {
        if (s[c - 'a']) {
          --ans;
          break;
        }
      }
      ++ans;
    }
    return ans;
  }

  vector<string> split(const string& s, char c) {
    vector<string> ans;
    string t;
    for (char d : s) {
      if (d == c) {
        ans.push_back(t);
        t.clear();
      } else {
        t.push_back(d);
      }
    }
    ans.push_back(t);
    return ans;
  }
};

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
}

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;
}

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
  }
}