Easy

题目描述

有一个键盘，其中某些字母键不能正常工作。键盘上的其他键都能正常工作。

给你一个由单个空格分隔的单词组成的字符串 text（没有前导或尾随空格），以及一个字符串 brokenLetters，其中包含所有损坏的不同字母键，返回你可以使用这个键盘完全输入的 text 中单词的数目。

示例 1：

输入：text = "hello world", brokenLetters = "ad"
输出：1
解释：由于 'd' 键损坏，我们无法输入 "world"。

示例 2：

输入：text = "leet code", brokenLetters = "lt"
输出：1
解释：由于 'l' 和 't' 键损坏，我们无法输入 "leet"。

示例 3：

输入：text = "leet code", brokenLetters = "e"
输出：0
解释：由于 'e' 键损坏，我们无法输入任何单词。

约束条件：

  • 1 <= text.length <= 10^4
  • 0 <= brokenLetters.length <= 26
  • text 由单个空格分隔的单词组成，没有前导或尾随空格
  • 每个单词只包含小写英文字母
  • brokenLetters 由不同的小写英文字母组成

提示：

  • 分别检查每个单词是否可以被输入
  • 只有当单词的所有字母都没有损坏时，该单词才能被输入

解题思路

解题思路

这是一道字符串处理的简单题目，核心思路是检查每个单词是否包含损坏的字母。

基本思路：

  1. 将损坏的字母存储到哈希集合中，便于快速查找
  2. 将文本按空格分割成单词数组
  3. 遍历每个单词，检查是否包含损坏的字母
  4. 如果单词中所有字母都不在损坏字母集合中，则该单词可以完全输入

优化方案：

  • 使用哈希集合存储损坏字母，查找时间复杂度为 O(1)
  • 也可以使用布尔数组标记损坏字母，空间换时间

实现细节：

  • 遍历单词时，一旦发现损坏字母就可以立即跳过该单词（短路优化）
  • 注意处理空字符串的边界情况

这种方法时间复杂度为 O(n)，其中 n 是文本总长度，空间复杂度为 O(k)，其中 k 是损坏字母的数量。

代码实现

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        unordered_set<char> broken(brokenLetters.begin(), brokenLetters.end());
        
        stringstream ss(text);
        string word;
        int count = 0;
        
        while (ss >> word) {
            bool canType = true;
            for (char c : word) {
                if (broken.count(c)) {
                    canType = false;
                    break;
                }
            }
            if (canType) count++;
        }
        
        return count;
    }
};

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        broken = set(brokenLetters)
        words = text.split()
        count = 0
        
        for word in words:
            if not any(c in broken for c in word):
                count += 1
        
        return count

public class Solution {
    public int CanBeTypedWords(string text, string brokenLetters) {
        var broken = new HashSet<char>(brokenLetters);
        var words = text.Split(' ');
        int count = 0;
        
        foreach (var word in words) {
            bool canType = true;
            foreach (char c in word) {
                if (broken.Contains(c)) {
                    canType = false;
                    break;
                }
            }
            if (canType) count++;
        }
        
        return count;
    }
}

var canBeTypedWords = function(text, brokenLetters) {
    const broken = new Set(brokenLetters);
    const words = text.split(' ');
    let count = 0;
    
    for (const word of words) {
        let canType = true;
        for (const c of word) {
            if (broken.has(c)) {
                canType = false;
                break;
            }
        }
        if (canType) count++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n 为文本总长度，需要遍历所有字符
空间复杂度O(k)k 为损坏字母数量，用于存储损坏字母集合