3330. Find the Original Typed String I

發表於

用來測試程式碼 highlight 的文章 ><。

Approach

紀錄每個連續的 substring 長度，把它加到答案中。但這樣會多算，因為每個可能多打的片段，都有算到”原本字串”的可能性，因此需要扣掉連續字元 substring 的數目減掉 1，此即為正確答案。

Complexity

$$O(n)$$

Code (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int possibleStringCount(string word) {
        int ret = 0;
        int seqcnt = 0;
        int cur = 1;
        char prev = word[0];
        int n = word.size();
        for (int i = 1; i < n; i++) {
            if (word[i] == prev) {
                ++cur;
            } else {
                if (cur > 1) {
                    ret += cur;
                    seqcnt++;
                }
                cur = 1;
                prev = word[i];
            }
        }
        if (cur > 1) {
            ret += cur-1;
        }
        if (ret == 0) return 1;
        ret -= seqcnt-1;
        return ret;
    }
};