3330. 找到初始输入字符串 I

题目描述

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 只包含小写英文字母。

解法

方法一：直接遍历

根据题目描述，如果所有相邻字符都不相同，那么只有 1 种可能的输入字符串；如果有 1 对相邻字符相同，例如 "abbc"，那么可能的输入字符串有 2 种："abc" 和 "abbc"。

依此类推，如果有 \(k\) 对相邻字符相同，那么可能的输入字符串有 \(k + 1\) 种。

因此，我们只需要遍历字符串，统计相邻字符相同的对数再加 1 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def possibleStringCount(self, word: str) -> int:
        return 1 + sum(x == y for x, y in pairwise(word))

class Solution {
    public int possibleStringCount(String word) {
        int f = 1;
        for (int i = 1; i < word.length(); ++i) {
            if (word.charAt(i) == word.charAt(i - 1)) {
                ++f;
            }
        }
        return f;
    }
}

class Solution {
public:
    int possibleStringCount(string word) {
        int f = 1;
        for (int i = 1; i < word.size(); ++i) {
            f += word[i] == word[i - 1];
        }
        return f;
    }
};

func possibleStringCount(word string) int {
    f := 1
    for i := 1; i < len(word); i++ {
        if word[i] == word[i-1] {
            f++
        }
    }
    return f
}

function possibleStringCount(word: string): number {
    let f = 1;
    for (let i = 1; i < word.length; ++i) {
        f += word[i] === word[i - 1] ? 1 : 0;
    }
    return f;
}

impl Solution {
    pub fn possible_string_count(word: String) -> i32 {
        1 + word.as_bytes().windows(2).filter(|w| w[0] == w[1]).count() as i32
    }
}

3330. 找到初始输入字符串 I

题目描述

解法

方法一：直接遍历

评论