字符串 | Bo Peng

翻转

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。

示例1：

 输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
 

示例2：

 输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
 

提示：

1 <= s.length <= 10⁵
s[i]都是ASCII码表中的可打印字符

Solution

本题比较简单，只需要使用双指针交换s中的元素即可。

题目链接：

python代码：

 class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """

        left, right = 0, len(s)-1

        while left < right:
            s[left], s[right] = s[right], s[left]

            left += 1
            right-= 1
 

C++代码：

 class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0, j = s.size()-1;

        while (i < j) {
            swap(s[i], s[j]);

            ++i;
            --j;
        }
    }
};
 

541. 反转字符串 II

给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。

如果剩余字符少于k个，则将剩余字符全部反转。
如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。

示例1：

 输入：s = "abcdefg", k = 2
输出："bacdfeg"
 

示例2：

 输入：s = "abcd", k = 2
输出："bacd"
 

提示：

1 <= s.length <= 10⁴
s仅由小写英文组成
1 <= k <= 10⁴

Solution

本题与反转字符串基本一致，只需要在遍历时每次取大小为2*k的窗口并反转其中的前k个元素即可。不过需要注意python中字符串是不可变对象(immutable)无法直接进行修改，我们必须先将s转换为列表进行反转，然后将反转后的列表转换为字符串输出。

题目链接：

python代码：

 class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        ss = list(s)
        N = len(ss)

        for i in range(0, N, 2*k):
            ss[i:i+k] = ss[i:i+k][::-1]

        return "".join(ss)
 

C++代码：

 class Solution {
public:
    string reverseStr(string s, int k) {
        int N = s.length();

        for (int i = 0; i < N; i += 2*k) {
            reverse(s.begin()+i, s.begin()+min(i+k, N));
        }

        return s;
    }
};
 

151. 反转字符串中的单词

给你一个字符串s，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例1：

 输入：s = "the sky is blue"
输出："blue is sky the"
 

示例2：

 输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
 

示例3：

 输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
 

提示：

1 <= s.length <= 10⁴
s包含英文大小写字母、数字和空格' '
s中至少存在一个单词

Solution

本题的解法可以分为3步：

去掉字符串中多余的空格' '
将整个字符串反转
将字符串中的每个单词反转

为了去除掉字符串中多余的空格，这里定义一个辅助函数removeExtraSpace()通过双指针来进行遍历：

使用left指针去掉字符串开头的空格
使用right指针去掉字符串末尾的空格
对字符串中间部分进行遍历，如果遇到非空格则把字符加入到res中否则继续前进直到遇到下一个非空格字符

removeExtraSpace()代码可参考如下。

 def removeExtraSpace(s: List[str]) -> List[str]:
    left, right = 0, len(s)-1

    while s[left] == " ":
        left += 1
    
    while s[right] == " ":
        right -= 1
    
    res = []

    while left <= right:
        if s[left] != " ":
            res.append(s[left])
            left += 1
        else:
            while s[left] == " ":
                left += 1

            res.append(" ")

    return res
 

除了removeExtraSpace()之外我们再定义一个辅助函数reverse()用来反转指定区间内的字符，代码可参考如下：

 def reverse(s: List[str], left: int, right: int) -> List[str]:
    while left < right:
        s[left], s[right] = s[right], s[left]

        left += 1
        right-= 1
    
    return s
 

这样在第二步反转整个字符串中我们只需要指定left = 0以及right = len(ss)-1即可。

而在第三步我们需要将空格分割的单词分别进行反转。为了方便处理，我们在整体反转的字符串ss后面添加一个空格，这样所有的单词都是以空格结尾。然后利用双指针left指向每个单词开头，right指向单词结尾的空格进行反转即可。

 ## reverse each word
left = right = 0
for right in range(len(ss)):
    if ss[right] == " ":
        ss = reverse(ss, left, right)
        left = right + 1
 

最后需要注意的是反转每个单词后ss会以之前添加的空格作为开头，我们需要手动去掉它。整个流程的代码可以参考如下。

题目链接：

python代码：

 class Solution:
    def reverseWords(self, s: str) -> str:
        def removeExtraSpace(s: List[str]) -> List[str]:
            left, right = 0, len(s)-1

            while s[left] == " ":
                left += 1
            
            while s[right] == " ":
                right -= 1
            
            res = []

            while left <= right:
                if s[left] != " ":
                    res.append(s[left])
                    left += 1
                else:
                    while s[left] == " ":
                        left += 1

                    res.append(" ")

            return res
        
        def reverse(s: List[str], left: int, right: int) -> List[str]:
            while left < right:
                s[left], s[right] = s[right], s[left]

                left += 1
                right-= 1
            
            return s
        
        ss = list(s)
        
        ## remove extra space
        ss = removeExtraSpace(ss)

        ## reverse whole list
        ss = reverse(ss, 0, len(ss)-1)

        ## add an additional " " in the end
        ss.append(" ")

        ## reverse each word
        left = right = 0
        for right in range(len(ss)):
            if ss[right] == " ":
                ss = reverse(ss, left, right)
                left = right + 1
        
        ## remove the additional " " in the beginning
        ss = ss[1:]

        return "".join(ss)
 

C++代码：

 class Solution {
public:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i], s[j]);

            ++i;
            --j;
        }
    }

    void removeExtraSpace(string& s) {
        int slow = 0;
        for (int fast = 0; fast < s.size(); ++fast) {
            if (s[fast] != ' ') {
                if (slow != 0) {
                    s[slow] = ' ';
                    ++slow;
                }

                while (fast < s.size() && s[fast] != ' ') {
                    s[slow] = s[fast];

                    ++fast;
                    ++slow;
                }
            }
        }

        s.resize(slow);
    }

    string reverseWords(string s) {
        removeExtraSpace(s);
        
        int N = s.size();
        reverse(s, 0, N-1);

        int left = 0;
        for (int right = 0; right <= N; ++right) {
            if (s[right] == ' ' || right == N) {
                reverse(s, left, right-1);
                left = right+1;
            }
        }

        return s;
    }
};
 

当然如果允许使用库函数的话可以直接利用s.split(" ")对字符串进行分割，然后再对分割后的每个单词进行反转并组合成新的字符串输出即可。

 class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))
 

剑指Offer 58-II.左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例1：

 输入: s = "abcdefg", k = 2
输出: "cdefgab"
 

示例2：

 输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
 

限制：

1 <= k < s.length <= 10000

Solution

本题解法类似于轮转数组。我们需要先反转前n个字符以及末尾的N-n个字符，最后反转整个字符串即可。

题目链接：

python代码：

 class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        def reverse(s: List[str], left: int, right: int) -> List[str]:
            while left < right:
                s[left], s[right] = s[right], s[left]

                left += 1
                right-= 1
            
            return s
        
        ss = list(s)
        N  = len(ss)

        ss = reverse(ss, 0, n-1)
        ss = reverse(ss, n, N-1)
        ss = reverse(ss, 0, N-1)

        return "".join(ss)
 

C++代码：

 class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin()+n);
        reverse(s.begin()+n, s.end());
        reverse(s.begin(), s.end());

        return s;
    }
};
 

当然本题也可以直接通过对字符串进行索引和拼接来实现。

 class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]
 

7. 整数反转

给你一个32位的有符号整数x ，返回将x中的数字部分反转后的结果。

如果反转后整数超过32位的有符号整数的范围[−2³¹, 2³¹ − 1]，就返回0。

假设环境不允许存储64位整数(有符号或无符号)。

示例1：

 输入：x = 123
输出：321
 

示例2：

 输入：x = -123
输出：-321
 

示例3：

 输入：x = 120
输出：21
 

示例4：

 输入：x = 0
输出：0
 

提示：

-2³¹ <= x <= 2³¹ - 1

Solution

本题的难点在于如何考虑32位整数的范围以及负数的情况。假设x > 0且反转后不会出现溢出的问题，我们只需要不断取出x的末位数字并放到res的末尾即可。

接下来考虑32位数字溢出的问题。记32位整数的上下界分别为INT_MIN = -(1 << 31)与INT_MAX = (1 << 31) - 1，如果res < INT_MIN // 10 + 1或res > INT_MAX // 10时会出现溢出，因此需要在更新res前进行判断。

最后是负数的情况。这里需要注意的是python中取模和取余运算对于负数与其它常见编程语言不同，digit = x % 10在x < 0的情况下会返回[0, 9)，因此我们需要令digit -= 10才能得到所需的末位数字。

题目链接：

python代码：

 class Solution:
    def reverse(self, x: int) -> int:        
        INT_MIN, INT_MAX = -(1 << 31), (1 << 31) - 1

        res = 0
        while x:
            if res < INT_MIN // 10 + 1 or res > INT_MAX // 10:
                return 0
            
            digit = x % 10
            if x < 0 and digit > 0:
                digit -= 10

            x = (x - digit) // 10
            res = res * 10 + digit

        return res
 

C++代码：

 class Solution {
public:
    int reverse(int x) {
        int res = 0;

        while (x) {
            if (res < INT_MIN / 10 || res > INT_MAX / 10) {
                return 0;
            }

            res = res * 10 + x % 10;
            x = x / 10;
        }

        return res;
    }
};
 

替换字符

剑指Offer 05.替换空格

请实现一个函数，把字符串s中的每个空格替换成”%20”。

示例1：

 输入：s = "We are happy."
输出："We%20are%20happy."
 

限制：

0 <= s 的长度 <= 10000

Solution

本题的解法在于从后向前对字符串进行遍历。当s[i] == " "时，字符串s会被分割为未遍历的s[:i]以及完成空格替换的s[i+1:]两部分，此时我们可以更新字符串s = s[:i] + "%20" + s[i+1:]来完成对空格的替换。而继续遍历时i会向前指向未遍历的部分，这样就无需考虑s更新后改变的长度。

题目链接：

python代码：

 class Solution:
    def replaceSpace(self, s: str) -> str:
        N = len(s)

        for i in range(N-1, -1, -1):
            if s[i] == " ":
                s = s[:i] + "%20" + s[i+1:]
        
        return s
 

C++代码：

 class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, N = s.size();

        for (auto& ch : s) {
            if (ch == ' ') ++count;
        }

        s.resize(count*2 + N);
        int i = N-1, j = s.size()-1;

        while (i < j) {
            if (s[i] != ' ') {
                s[j] = s[i];
            } else {
                s[j-2] = '%';
                s[j-1] = '2';
                s[j]   = '0';

                j -= 2;
            }

            --i;
            --j;
        }

        return s;
    }
};
 

当然本题也可以使用字符串的内置函数来进行处理。

 class Solution:
    def replaceSpace(self, s: str) -> str:        
        return "%20".join(s.split(" "))
 

KMP

28. 找出字符串中第一个匹配项的下标

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1 。

示例1：

 输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
 

示例2：

 输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 

提示：

1 <= haystack.length, needle.length <= 10⁴
haystack和needle仅由小写英文字符组成

Solution

KMP算法是处理字符串匹配的经典算法，它的目标是计算模式串needle在文本串haystack中第一次出现的位置。在介绍KMP算法前先看一下本题的暴力解法。我们可以把文本串haystack中每一个字符都当做一个可能的起点，然后在大小为N = len(needle)的窗口中进行每一个字符的比较。如果在比较中发现字符不匹配则说明无法在当前窗口中完成匹配，此时需要向右移动一位窗口并重新比较；而如果在窗口中完成了所有字符的匹配则直接返回窗口起始位置即可。整个算法流程可以参考如下。

题目链接：

 class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        M = len(haystack)
        N = len(needle)

        for idx in range(M-N+1):
            i = j = 0

            while j < N and haystack[idx+i] == needle[j]:
                i += 1
                j += 1
            
            if j == N:
                return idx
        
        return -1
 

显然暴力匹配算法的复杂度为O(MN)，它的缺陷在于每当出现匹配失败就需要移动窗口重新进行匹配。实际上当模式串中的字符needle[j]无法完成匹配时我们无需将j指针移动到模式串开头，而是可以利用已知的匹配信息将它移动到前面的一个可以继续进行匹配的位置。这样可以避免大量的重复计算，提高匹配效率。

KMP算法使用了前缀表(prefix table)来实现上述功能，它一般记为NEXT。前缀表NEXT记录了模式串needle与文本串haystack不匹配的时候，模式串应该从哪里开始重新匹配。换句话说，当haystack[i] != needle[j]时只需令j = NEXT[j-1]继续进行匹配即可。整个匹配逻辑可参考如下。

 i, j = 0, 0
while i < len(haystack):
    if haystack[i] == needle[j]:
        i += 1
        j += 1
    elif j > 0:
        j = NEXT[j-1]
    else:
        i += 1
    
    if j == len(needle):
        return i-j

return -1
 

NEXT[j]的意义是needle[j]结尾的子串所具有的最长相等前后缀长度。注意这里前缀是指不包含字符串末位的以第一个字符开头的子串，而后缀则是不包含字符串首位的以最后一个字符结尾的子串。因此，NEXT[j] = k表示以needle[j]结尾的子串其开头k个字符与末尾k个字符完全相同。这样当haystack[i] != needle[j]时以needle[j-1]结尾的子串其末尾NEXT[j-1]恰好匹配能匹配NEXT[j-1]个字符，我们只需要令j = NEXT[j-1]就可以继续进行匹配。

接下来考虑如何构造前缀表NEXT。这里我们需要使用双指针来进行处理，其中i指针对needle进行遍历而j指针则指向needle[i]结尾的最长相等前后缀末位的下一位。对于基本情况i == 0时前后缀都是空字符，因此令NEXT[i] = 0以及j = 0；继续遍历时需要分情况讨论：

如果needle[i] == needle[j]，说明可以把needle[j]添加到相等前后缀中，令j += 1
如果needle[i] != needle[j]，说明无法把needle[j]添加到相等前后缀中，令j = NEXT[j-1]继续向前寻找相等前后缀直到完成匹配

最后更新NEXT[i] = j得到最长相等前后缀的长度。整个构造前缀表NEXT的代码可参考如下。

 def buildNEXT() -> List[int]:
    NEXT = [0 for _ in needle]

    i = j = 0
    for i in range(1, len(needle)):
        while j > 0 and needle[i] != needle[j]:
            j = NEXT[j-1]

        if needle[i] == needle[j]:
            j += 1
        
        NEXT[i] = j

    return NEXT
 

把构造前缀表NEXT和利用NEXT进行匹配的代码结合到一起就实现了KMP算法，它的时间复杂度为O(M+N)远小于暴力算法的O(MN)。

题目链接：

 class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def buildNEXT() -> List[int]:
            NEXT = [0 for _ in needle]

            i = j = 0
            for i in range(1, len(needle)):
                while j > 0 and needle[i] != needle[j]:
                    j = NEXT[j-1]

                if needle[i] == needle[j]:
                    j += 1
                
                NEXT[i] = j

            return NEXT

        NEXT = buildNEXT()

        i = j = 0
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif j > 0:
                j = NEXT[j-1]
            else:
                i += 1
            
            if j == len(needle):
                return i - j
        
        return -1
 

当然如果允许使用库函数则可以直接利用字符串的str.find()方法进行匹配。

题目链接：

 class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)
 

459. 重复的子字符串

给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成。

示例1：

 输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
 

示例2：

 输入: s = "aba"
输出: false
 

示例3：

 输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 

提示：

1 <= s.length <= 10⁴
s由小写英文字母组成

Solution

本题同样可以使用KMP算法进行处理，实际上只需要构造出前缀表NEXT就能够判断s是否由重复的字符串组成。回忆前缀表NEXT中每一位都表示s以该位置结尾的子串具有的最长相等前后缀长度，如果s由重复的字符串组成那么一定有NEXT[-1] > 0。更进一步假设s由n个长度为l的字符串通过重复组成，前缀表最后一位满足NEXT[-1] = m * l。由于后缀不包含s第一位字符，必然有m - n == 1，因此只需要再判断len(s)是否能被len(s)-NEXT[-1]整除即可。

题目链接：

 class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:        
        def buildNEXT() -> List[int]:
            NEXT = [0 for _ in s]

            i = j = 0
            for i in range(1, len(s)):
                while j > 0 and s[i] != s[j]:
                    j = NEXT[j-1]

                if s[i] == s[j]:
                    j += 1
                
                NEXT[i] = j

            return NEXT
        
        NEXT = buildNEXT()
        
        if NEXT[-1] > 0 and len(s) % (len(s)-NEXT[-1]) == 0:
            return True
        
        return False
 

双指针

925. 长按键入

你的朋友正在使用键盘输入他的名字name。偶尔，在键入字符c时，按键可能会被长按，而字符可能被输入1次或多次。

你将会检查键盘输入的字符typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True。

示例1：

 输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。
 

示例2：

 输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。
 

提示：

1 <= name.length, typed.length <= 1000
name和typed的字符都是小写字母

Solution

本题需要使用双指针来逐位比较name和typed两个字符串。

如果name[i] == typed[j]则两个指针在当前位置的字符完成匹配，继续比较
如果name[i] != typed[j]则需要进一步考虑是否在typed中出现重复输入：
- 如果typed[j] == typed[j - 1]说明发生了重复输入，此时需要继续移动j指针
- 否则说明无法完成字符匹配，直接返回False
完成遍历后需要考虑i指针是否移动到name末尾：
- 如果i == len(name)说明所有字符都匹配成功，返回True
- 否则说明无法完成字符匹配，返回False

整个算法过程可以参考如下。

题目链接：

python代码：

 class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i = j = 0
        m, n = len(name), len(typed)

        while j < n:
            if i < m and name[i] == typed[j]:
                i += 1
                j += 1
            elif j >= 1 and typed[j] == typed[j - 1]:
                j += 1
            else:
                return False
                
        return i == m
 

C++代码：

 class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;

        while (j < typed.size()) {
            if (name[i] == typed[j]) {
                ++i;
                ++j;
            } else if (j > 0 && typed[j] == typed[j-1]) {
                ++j;
            } else return false;
        }

        return i==name.size();
    }
};
 

844. 比较含退格的字符串

同844. 比较含退格的字符串。

Solution

题目链接：

python代码：

 class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def backspace(s: List[str]) -> List[str]:
            fast, slow = 0, 0
            for fast in range(len(s)):
                if s[fast] != "#":
                    s[slow] = s[fast]
                    slow += 1
                elif slow > 0:
                    slow -= 1
            
            return s[:slow]
        
        return backspace(list(s)) == backspace(list(t))
 

C++代码：

 class Solution {
public:
    bool backspaceCompare(string s, string t) {
        removeBackSpace(s);
        removeBackSpace(t);

        return s == t;
    }

    void removeBackSpace(string &s) {
        int slow = 0;
        for (int fast = 0; fast < s.size(); ++fast) {
            if (s[fast] == '#') {
                if (slow > 0) --slow;
            } else {
                s[slow] = s[fast];
                ++slow;
            }
        }

        s.resize(slow);
    }
};
 

38. 外观数列

给定一个正整数n，输出外观数列的第n项。

「外观数列」是一个整数序列，从数字1开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n)是对countAndSay(n-1)的描述，然后转换成另一个数字字符串。

前五项如下：

 1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
 

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串"3322251"的描述如下图：

示例1：

 输入：n = 1
输出："1"
解释：这是一个基本样例。
 

示例2：

 输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
 

提示：

1 <= n <= 30

Solution

本题需要使用到递归和双指针来进行处理。首先考虑递归部分，当n == 1时返回基本样例"1"，而在其它情况下则需要调用自身countAndSay(n-1)得到待描述的字符串s。

接下来使用双指针对s进行描述。这里利用快慢指针fast和slow维护具有相同字符的区间并用快指针fast进行遍历，当s[fast] != s[slow]时计算区间的长度并把s[slow]添加到res中，res += str(fast-slow) + s[slow]。需要注意的是fast完成遍历时要把末尾的区间也添加到res中，res += str(fast-slow+1) + s[slow]。整个算法流程可以参考如下。

题目链接：

python代码：

 class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        
        s = self.countAndSay(n-1)
        res = ""

        fast = slow = 0
        for fast in range(len(s)):
            if s[fast] != s[slow]:
                res += str(fast-slow) + s[slow]

                slow = fast
        
        res += str(fast-slow+1) + s[slow]

        return res
 

C++代码：

 class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return string("1");

        auto s = countAndSay(n-1);
        string res = "";

        int slow = 0, fast = 0;
        for (fast = 0; fast < s.size(); ++fast) {
            if (s[fast] != s[slow]) {
                res += to_string(fast-slow) + s[slow];
                slow = fast;
            }
        }

        res = res + to_string(fast-slow) + s[slow];

        return res;
    }
};
 

翻转

344. 反转字符串

Solution

541. 反转字符串 II

Solution

151. 反转字符串中的单词

Solution

剑指Offer 58-II.左旋转字符串

Solution

7. 整数反转

Solution

替换字符

剑指Offer 05.替换空格

Solution

KMP

28. 找出字符串中第一个匹配项的下标

Solution

459. 重复的子字符串

Solution

双指针

925. 长按键入

Solution

844. 比较含退格的字符串

Solution

38. 外观数列

Solution

Reference