[LeetCode] 3330. Find the Original Typed String I
Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.
Although Alice tried to focus on her typing, she is aware that she may still have done this at most once.
You are given a string word, which represents the final output displayed on Alice’s screen.
Return the total number of possible original strings that Alice might have intended to type.
Example 1:
Input: word = “abbcccc”
Output: 5
Explanation:
The possible strings are: “abbcccc”, “abbccc”, “abbcc”, “abbc”, and “abcccc”.
Example 2:
Input: word = “abcd”
Output: 1
Explanation:
The only possible string is “abcd”.
Example 3:
Input: word = “aaaa”
Output: 4
Constraints:
1 <= word.length <= 100
word consists only of lowercase English letters.
找到初始输入字符串 I。
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙,她 可能 在一个按键上按太久,导致一个字符被输入 多次 。尽管 Alice 尽可能集中注意力,她仍然可能会犯错 至多 一次。
给你一个字符串 word ,它表示 最终 显示在 Alice 显示屏上的结果。
请你返回 Alice 一开始可能想要输入字符串的总方案数。
思路
这道题不涉及算法,注意观察字符串的规律。如果相邻的字符相同,那么第二个字母就有可能是一次重复的输入。所以我们可以遍历 input 字符串,如果当前字母跟前一个字母不一样,则说明没有犯错;如果跟前一个字母一样,那么第二个字母就有可能是因为犯错而输入的,则计数加一。
复杂度
时间O(n)
空间O(1)
代码
Java实现
1 |
|