Easy

题目描述

Alice 正在尝试在她的计算机上输入一个特定的字符串。然而，她往往比较笨拙，可能会按键时间过长，导致字符被多次输入。

尽管 Alice 试图专注于她的输入，但她知道自己最多可能犯一次这样的错误。

给你一个字符串 word，它表示 Alice 屏幕上显示的最终输出。

返回 Alice 可能想要输入的原始字符串的总数。

示例 1：

输入：word = "abbcccc"
输出：5
解释：可能的字符串有："abbcccc", "abbccc", "abbcc", "abbc", "abcccc"。

示例 2：

输入：word = "abcd"
输出：1
解释：唯一可能的字符串是 "abcd"。

示例 3：

输入：word = "aaaa"
输出：4

约束条件：

  • 1 <= word.length <= 100
  • word 仅由小写英文字母组成

提示：

  • 任何连续字符组都可能是错误输入的结果

解题思路

这道题的核心思路是找到所有可能的原始字符串数量。由于Alice最多只会犯一次错误（即某个字符被重复输入），我们需要考虑以下情况：

  1. 没有错误：原始字符串就是当前的 word
  2. 有错误：在某个连续重复字符段中删除一些字符

解题步骤：

  1. 首先统计结果为1（原字符串本身）
  2. 遍历字符串，找到所有连续相同字符的段
  3. 对于每个长度大于1的连续段，我们可以删除1到(长度-1)个字符，每种删除方式都产生一个可能的原始字符串
  4. 将所有可能的删除数量相加

例如对于"abbcccc"：

  • “bb"段可以删除1个字符 → “ab”
  • “cccc"段可以删除1、2、3个字符 → “ccc”、“cc”、“c”
  • 总共：1(原串) + 1(bb段) + 3(cccc段) = 5

时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int possibleStringCount(string word) {
        int count = 1; // 原字符串本身
        int n = word.length();
        
        for (int i = 0; i < n; ) {
            int j = i;
            // 找到连续相同字符的结束位置
            while (j < n && word[j] == word[i]) {
                j++;
            }
            // 如果连续字符长度大于1，可以删除1到(长度-1)个字符
            if (j - i > 1) {
                count += (j - i - 1);
            }
            i = j;
        }
        
        return count;
    }
};

class Solution:
    def possibleStringCount(self, word: str) -> int:
        count = 1  # 原字符串本身
        n = len(word)
        i = 0
        
        while i < n:
            j = i
            # 找到连续相同字符的结束位置
            while j < n and word[j] == word[i]:
                j += 1
            # 如果连续字符长度大于1，可以删除1到(长度-1)个字符
            if j - i > 1:
                count += (j - i - 1)
            i = j
        
        return count

public class Solution {
    public int PossibleStringCount(string word) {
        int count = 1; // 原字符串本身
        int n = word.Length;
        
        for (int i = 0; i < n; ) {
            int j = i;
            // 找到连续相同字符的结束位置
            while (j < n && word[j] == word[i]) {
                j++;
            }
            // 如果连续字符长度大于1，可以删除1到(长度-1)个字符
            if (j - i > 1) {
                count += (j - i - 1);
            }
            i = j;
        }
        
        return count;
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var possibleStringCount = function(word) {
    let count = 1; // 原字符串本身
    const n = word.length;
    
    for (let i = 0; i < n; ) {
        let j = i;
        // 找到连续相同字符的结束位置
        while (j < n && word[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度，需要遍历一次字符串
空间复杂度O(1)，只使用了常数级别的额外空间

相关题目