1935.可以输入的最大单词数：哈希表

【LetMeFly】1935.可以输入的最大单词数：哈希表

力扣题目链接：https://leetcode.cn/problems/maximum-number-of-words-you-can-type/

键盘出现了一些故障，有些字母键无法正常工作。而键盘上所有其他键都能够正常工作。

给你一个由若干单词组成的字符串 text ，单词间由单个空格组成（不含前导和尾随空格）；另有一个字符串 brokenLetters ，由所有已损坏的不同字母键组成，返回你可以使用此键盘完全输入的 text 中单词的数目。

 

示例 1：

输入：text = "hello world", brokenLetters = "ad"
输出：1
解释：无法输入 "world" ，因为字母键 'd' 已损坏。

示例 2：

输入：text = "leet code", brokenLetters = "lt"
输出：1
解释：无法输入 "leet" ，因为字母键 'l' 和 't' 已损坏。

示例 3：

输入：text = "leet code", brokenLetters = "e"
输出：0
解释：无法输入任何单词，因为字母键 'e' 已损坏。

 

提示：

• 1 <= text.length <= 104
• 0 <= brokenLetters.length <= 26
• text 由若干用单个空格分隔的单词组成，且不含任何前导和尾随空格
• 每个单词仅由小写英文字母组成
• brokenLetters 由 互不相同 的小写英文字母组成

解题方法：哈希表

首先把brokenLetters变成一个哈希表用来快速查询一个字符是否已经broken。

接着使用一个变量can表示当前单词中是否有不可用字符，默认值为true。

遍历字符串text，如果遇到空格，就说明遍历完了一个单词，若单词中没有不可用字符则答案累加；之后将can重置为true。

否则，如果遇到的字符在broken列表中，就将can置为false。

• 时间复杂度$O(len(text) + len(brokenLetters))$
• 空间复杂度$O(len(brokenLetters))$

也可以手动实现哈希表，如使用一个整数的不同位代表不同字符是否在哈希表中。

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-09-15 21:48:46
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-15 21:50:18
 */
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        unordered_set<char> cannot(brokenLetters.begin(), brokenLetters.end());
        int ans = 0;
        bool can = true;
        for (char c : text) {
            if (c == ' ') {
                ans += can;
                can = true;
                continue;
            }
            if (cannot.count(c)) {
                can = false;
            }
        }
        return ans + can;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-09-15 21:48:47
LastEditors: LetMeFly.xyz
LastEditTime: 2025-09-15 21:56:54
'''
class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        ans = 0
        cannot = set(brokenLetters)
        for word in text.split():
            ans += all(c not in cannot for c in word)
        return ans

Python

'''
Author: LetMeFly
Date: 2025-09-15 21:58:43
LastEditors: LetMeFly.xyz
LastEditTime: 2025-09-15 21:58:57
'''
class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        cannot = set(brokenLetters)
        return sum(all(c not in cannot for c in word) for word in text.split())

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-09-15 21:48:47
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-15 22:00:30
 */
import java.util.Set;
import java.util.HashSet;

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        Set<Character> cannot = new HashSet<>();
        for (char c : brokenLetters.toCharArray()) {
            cannot.add(c);
        }
        int ans = 0;
        boolean can = true;
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                ans += can ? 1 : 0;
                can = true;
                continue;
            }
            if (cannot.contains(c)) {
                can = false;
            }
        }
        return ans + (can ? 1 : 0);
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-09-15 21:48:47
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-15 22:06:31
 */
package main

func canBeTypedWords(text string, brokenLetters string) (ans int) {
    cannot := map[byte]struct{}{}
    for i := range brokenLetters {
        cannot[brokenLetters[i]] = struct{}{}
    }
    can := true
    for i := range text {
        if text[i] == ' ' {
            if can {
                ans++
            } else {
                can = true
            }
            continue
        }
        if _, in := cannot[text[i]]; in {
            can = false
        }
    }
    if can {
        ans++
    }
    return
}

Rust

/*
 * @Author: LetMeFly
 * @Date: 2025-09-15 21:48:47
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-15 22:11:40
 */
use std::collections::HashSet;

impl Solution {
    pub fn can_be_typed_words(text: String, broken_letters: String) -> i32 {
        let cannot: HashSet<char> = broken_letters.chars().collect();
        let mut ans: i32 = 0;
        let mut can: bool = true;
        for c in text.chars() {
            if c == ' ' {
                ans += if can { 1 } else { 0 };
                can = true;
            } else if cannot.contains(&c) {
                can = false;
            }
        }
        ans + if can { 1 } else { 0 }
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源