原文链接: https://leetcode-cn.com/problems/maximum-number-of-words-you-can-type

英文原文

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.

中文题目

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

给你一个由若干单词组成的字符串 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 由 互不相同 的小写英文字母组成

通过代码

高赞题解

思路： 枚举，哈希

时间复杂度： $O(n+m)$，$n$ 为 text 的长度，$m$ 为故障键位的数量。

考虑text仅有一个单词的情况：

• 初始化标记变量 flag = true。
• 遍历 text 的每个字符 c。
• c 为故障则设置 flag = false。

考虑text包含多个单词的情况。单词由单个空格切分，且单词不含任何前导和尾随空格。

因此在遍历 text 的过程中，若 c 为空格或 \0，则标记一个单词的结束。此时可根据 flag 的值更新答案，并重置 flag。

复杂度分析

考虑判断c是否故障的两种方法。

第一种，暴力枚举

每次判断需遍历一遍 brokenLetters，时间复杂度：$O(m)$。一共需要判断 $n$ 次，因此整体的时间复杂度为 $O(n*m)$。没有使用额外的空间，空间复杂度故为 O(1)。

第二种，哈希数组

预先遍历一遍 brokenLetters，初始化哈希数组，时间复杂度为 $O(m)$，空间复杂度为 $O(m)$。

借助哈希数组判断 c 为是否为故障的，可将单词判断的时间复杂度降至$O(1)$。

因此整体时间复杂度为$O(n+m)$：

• $O(m)$：遍历 brokenLetters，初始化哈希数组。
• $O(n)$：遍历 text 计算答案。

class Solution {
public:
    int canBeTypedWords(string text, string bl) {
        bool mark[26] = {0};
        for (auto c : bl) {
            mark[c-'a'] = true;
        }
        bool flag = true;
        int cnt = 0;
        for (int i = 0; i <= text.size(); i++) {
            // 遇到了空格或 \0，表明一个单词遍历完了，
            if (text[i] == ' ' || text[i] == '\0') {
                if (flag) cnt++; // 根据 flag 更新答案
                flag = true; // 重置 flag
            } else if (mark[text[i]-'a']) {
                flag = false; // 键位坏掉了
            }
        }
        return cnt;
    }
};

统计信息

通过次数	提交次数	AC比率
7367	10031	73.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言