Lesson8 字符串循环+切片/字符串数学运算专题

1. 字符串循环+切片

例题讲解

LC14 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

题目分析

要找到字符串数组中的最长公共前缀，我们可以依次比较每个字符串的字符，直到找到不匹配的位置为止。这个问题可以通过多种方法解决，比如纵向扫描、横向扫描、分治法、二分查找等。我们这里采用一种较为直观的横向扫描法。

思路

边界情况:
如果字符串数组为空，直接返回空字符串。
如果字符串数组只有一个字符串，那么最长公共前缀就是这个字符串本身。
从第一个字符串开始:
假设第一个字符串是最长公共前缀，接下来逐一与数组中的其他字符串进行比较。
每次比较时，逐字符地进行比较，直到找到不匹配的字符或比较完成一个字符串的所有字符。
更新当前的最长公共前缀为匹配的部分。
返回结果:
最后返回匹配后的公共前缀，如果没有匹配到任何前缀，则返回空字符串。

参考解答

C++
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string prefix = strs[0];  // 初始化最长公共前缀为第一个字符串

        // 依次与其他字符串进行比较
        for (int i = 1; i < strs.size(); ++i) {
            while (strs[i].find(prefix) != 0) {  // 当前前缀与下一个字符串进行比较
                prefix = prefix.substr(0, prefix.length() - 1);  // 不断缩短前缀
                if (prefix.empty()){
                    return "";  // 如果前缀为空，返回空字符串
                }
            }
        }
        return prefix;
    }
};

LC125. 验证回文串

问题描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true；否则，返回 false。

题目分析

回文串的判断要求忽略大小写、去除非字母数字字符。因此需要先进行字符过滤，然后判断处理后的字符串是否正着读和反着读都相同。

思路

1. 字符过滤
使用遍历的方式将字符串中的非字母数字字符过滤掉，并且将字母统一转换为小写，以便后续比较。

2. 反转判断
通过直接反转处理后的字符串，比较原字符串与其反转后的版本是否相等，如果相等则是回文串。

具体步骤

遍历过滤：创建一个空字符串 filteredString，遍历输入字符串 s，只保留字母和数字字符，并且将字母统一转换为小写。
反转比较：将 filteredString 反转，比较反转后的字符串与原字符串是否相同。如果相同，则返回 true，否则返回 false。

参考解答

C++
class Solution {
public:
    bool isPalindrome(string s) {
        string filteredString = "";

        // 遍历字符串，保留字母和数字字符，并将字母转换为小写
        for (char c : s) {
            if (isalnum(c)) {
                filteredString += tolower(c);  // 将字母转为小写
            }
        }

        // 创建一个反转后的字符串
        string reversedString = filteredString;
        reverse(reversedString.begin(), reversedString.end());

        // 判断原始过滤后的字符串与反转后的字符串是否相同
        return filteredString == reversedString;
    }
};

代码详解

isalnum(c)：该函数检查字符 c 是否为字母或数字。如果 c 是字母或数字，返回 true，否则返回 false。通过此函数，可以过滤掉空格、标点符号等无关字符。
tolower(c)：该函数将字母 c 转换为小写。这样能够确保在判断回文时忽略大小写差异。
reverse(reversedString.begin(), reversedString.end())：reverse 函数可以将字符串的顺序反转，从而实现正序与逆序比较。
比较 filteredString == reversedString：通过比较原字符串与其反转后的版本，判断是否为回文串。如果两者相等，则说明该字符串是回文串。

举一反三

LC459. 重复的子字符串

问题描述

给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。如果存在这样的子串，则返回 true，否则返回 false。

解题思路

要判断字符串是否由重复的子串构成，可以逐步检查可能的子串，并进行如下操作：

检查子串是否能整除字符串的长度：
- 如果字符串长度 n 可以被某个子串长度 i 整除，说明这个子串有可能是组成整个字符串的重复单元，因此可以进一步检查。
构造一个由子串重复构成的新字符串：
- 对于每种符合条件的子串，构造一个新字符串，这个新字符串由该子串重复多次得到，然后判断这个新字符串是否等于原始字符串。

参考解答

C++
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; ++i) {
            // 检查子串长度 i 是否能整除字符串长度 n
            if (n % i == 0) {
                string substring = s.substr(0, i);  // 提取长度为 i 的子串
                string repeated = "";  // 用来构造新字符串
                for (int j = 0; j < n / i; ++j) {
                    repeated += substring;  // 将子串重复拼接
                }
                // 如果拼接后的字符串与原字符串相同，返回 true
                if (repeated == s) {
                    return true;
                }
            }
        }
        return false;  // 没有找到合适的子串，返回 false
    }
};

详细讲解

s.substr(0, i):
- substr 函数用于从索引 0 开始提取一个长度为 i 的子串。例如，对于字符串 abcdef，当 i = 2 时，s.substr(0, 2) 返回 "ab"。
if (n % i == 0):
- 这段代码检查当前子串的长度 i 是否能整除字符串 s 的总长度 n。如果不能整除，说明该子串不可能是构成字符串的重复单元，跳过检查。
repeated += substring:
- 该步骤通过将提取的子串不断拼接，构造一个与原字符串等长的新字符串。如果子串长度为 i，并且 s 的长度为 n，就会将子串重复 n / i 次，以生成长度等于 n 的字符串。
比较生成的字符串与原字符串:
- 构造的字符串 repeated 和原字符串 s 进行比较，如果二者相等，说明字符串 s 是由该子串重复构成的，返回 true。
循环结束后的返回:
- 如果遍历完所有可能的子串都没找到合适的子串，说明字符串 s 不能通过重复某个子串构成，返回 false。

更高效的解法

可以利用字符串的特性来进一步优化：

将字符串 s 自身拼接一遍，得到 s + s。
去掉开头和结尾的字符，检查 s 是否在新的字符串中出现。
如果出现，说明 s 可以由某个子串构成。

优化示例代码

C++
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string doubled = s + s; // 将字符串拼接
        string subString = doubled.substr(1, doubled.size() - 2); // 去掉首尾字符
        return subString.find(s) != string::npos; // 检查是否包含原字符串
    }
};

证明：字符串拼接后掐头去尾可以用于判断重复的子字符串

补充：什么是前缀和后缀？

前缀（Prefix）：从字符串的开头开始的连续字符子串。例如，字符串 "abcde" 的前缀有：
前缀 1："a"
前缀 2："ab"
前缀 3："abc"
前缀 4："abcd"
前缀 5："abcde"（整个字符串本身也是一个前缀）
后缀（Suffix）：从字符串的结尾开始的连续字符子串。例如，字符串 "abcde" 的后缀有：
后缀 1："e"
后缀 2："de"
后缀 3："cde"
后缀 4："bcde"
后缀 5："abcde"（整个字符串本身也是一个后缀）

充分必要性证明

为了证明给定字符串 s 是由某个子串重复构成的充分必要性，我们需要从两个方向来进行证明：

充分性：如果一个字符串 s 是由某个子串重复构成的，那么在拼接后的字符串 s + s 中，掐头去尾后，一定能再次找到 s。
必要性：如果在掐头去尾的 s + s 中找到了 s，那么 s 一定是由某个子串重复构成的。

1. 充分性

假设：设字符串 s 是由一个较短的子串 p 重复多次构成的，即 s = p + p + ... + p（假设 p 重复 k 次）。

举例：比如 s = "abab"，这是由 p = "ab" 重复两次构成的。

拼接 s + s：我们将 s 拼接得到 s + s，例如：

Text Only
1	`s + s = "abababab"`

掐头去尾，去掉首尾字符，得到 new_s = (s + s).substr(1, (s+s).length() - 1)，对于上面的例子：

Text Only
1	`new_s = "bababa"`

寻找 s 在 new_s 中的出现：由于 s 是由子串 p 多次重复（至少两次）构成的，s + s 就会重复至少 4 次 p，掐头去尾后，重复至少 2 次 p，前缀和后缀必然有重叠，一定能再次找到 s。

Text Only
1 2	`new_s = "bababa" ^^^^ (这里找到 "abab")`

充分性证毕。

2. 必要性

假设：我们已经在去掉首尾字符的 s + s 中再次找到了 s。现在我们需要证明，s 一定是由某个子串重复构成的。

构造 new_s：首先，构造 new_s，其等价操作是 new_s = (s + s).substr(1, (s+s).length() - 1)。假设字符串 s 在 new_s 中匹配的位置从 i 开始，也就是说我们找到了一个偏移量 i，使得 s.substr(i) + s.substr(0, i) 和 s 完全相同。这意味着：

C++
s.substr(i) + s.substr(0, i) == s;

也就是说，s 的某个后缀与它的某个前缀重叠匹配。

举例说明：

Text Only
1 2	`s + s = "abababab" 去掉首尾字符后得到：new_s = "bababa"`

- s 的前缀有：'a', 'ab', 'aba', 'abab' - s 的后缀有：'b', 'ab', 'bab', 'abab'

可以发现，s = "abab" 在 "bababa" 中确实再次出现，且匹配发生在交界处（偏移量为1），这时 s 的前缀和后缀出现了重合。

这种现象说明 s 的前缀和后缀存在交替重叠，表明 s 具有周期性，意味着 s 是由一个较短的子串重复构成的。换句话说，如果 s 的前缀和后缀有某种重叠，形成了周期性，那么 s 就可以通过重复某个子串构成。

必要性证毕。

总结：

我们已经证明了：

充分性：如果 s 是由某个子串重复构成的，那么在 s + s 中掐头去尾后，一定能够再次找到 s。这是因为重复子串会使得前缀和后缀有重叠。
必要性：如果在掐头去尾的 s + s 中找到了 s，那么 s 一定是由某个子串重复构成的。这是因为只有当 s 具有周期性时，它的前缀和后缀才会交替重叠，形成匹配。

因此，拼接 s + s 并去掉首尾字符后能否再次找到 s，可以用来判断 s 是否由某个子串重复构成。

补充材料：

充分性及必要性证明

Leetcode官方题解证明

LC796 旋转字符串

问题描述

给定两个字符串 s 和 goal，如果通过若干次旋转操作之后，s 能变成 goal，则返回 true，否则返回 false。

旋转操作是将字符串的第一个字符移动到最后一位。例如，字符串 "abcde" 经过一次旋转变为 "bcdea"。

解题思路

理解旋转：
- 旋转操作是将字符串的第一个字符移动到最后一位。
- 例如，字符串 "abcde" 经过一次旋转变为 "bcdea"，再经过一次旋转变为 "cdeab"，如此类推。
字符串旋转的特性：
- 如果将字符串 s 拼接成 s + s，这个新字符串将包含 s 所有可能的旋转形式。
- 例如，s = "abcde" 拼接后变为 "abcdeabcde"，它包含了所有旋转形式："abcde", "bcdea", "cdeab", "deabc", "eabcd"。
判断 goal 是否是 s + s 的子串：
- 我们可以遍历 s + s，截取与 s 相同长度的子串，并检查它是否等于 goal。

示例代码

C++
class Solution {
public:
    bool rotateString(string s, string goal) {
        string double_s = s + s;

        // 遍历 double_s 中的每个子串，检查是否等于 goal
        for (int i = 0; i < s.length(); i++) {
            if (double_s.substr(i, s.length()) == goal) {
                return true;
            }
        }

        return false;
    }
};

代码讲解

double_s = s + s：将字符串 s 自身拼接，形成一个新字符串 double_s，其长度为 2 * s.length()。
遍历 double_s：
- 在 double_s 中，逐个提取长度为 s.length() 的子串，使用 substr(i, s.length()) 函数从索引 i 处开始截取与 s 相同长度的子串。
比较子串和 goal：
- 如果某个子串等于 goal，则返回 true，表示 s 通过旋转可以变为 goal。
返回 false：
- 如果遍历完所有可能的子串都没有匹配，则返回 false。

LC28 查找字符串中的第一个匹配项索引

问题描述

给定两个字符串 haystack 和 needle，你需要在 haystack 字符串中找出 needle 字符串出现的第一个位置（从 0 开始）。如果不存在，则返回 -1。

思路分析

如果 needle 为空字符串，直接返回 0。
遍历 haystack，从每个索引位置检查是否与 needle 匹配。
如果匹配成功，返回该索引，否则继续遍历。
如果遍历结束后未找到，返回 -1。

参考解答

C++
class Solution {
public:
    int strStr(string haystack, string needle) {
        // 如果 needle 为空字符串，直接返回 0
        if (needle.empty()) {
            return 0;
        }

        // 获取两个字符串的长度
        int n = haystack.length();
        int m = needle.length();

        // 遍历 haystack，直到剩余的部分长度小于 needle 长度
        for (int i = 0; i <= n - m; i++) {
            // 比较从 i 开始的子串是否等于 needle
            if (haystack.substr(i, m) == needle) {
                return i;
            }
        }

        // 如果遍历结束后没有找到，返回 -1
        return -1;
    }
};

2. 字符串数学运算

字符串数学模拟的基本解题思路主要涉及如何通过逐步操作和简单的数学运算，处理字符串形式的数字计算。

基本概念

字符转数字：
- 字符串中的数字是以字符的形式存在的，例如字符 '0' 到 '9'。
- 可以通过 char - '0' 将字符转为对应的数字。例如，'5' - '0' 的结果为 5。
进位处理：
- 在进行加法运算时，如果某一位的和大于或等于 10，则需要处理进位（carry），将 1 加到下一位的计算中。
- 进位的计算可以通过 carry = sum / 10 来实现，而当前位的结果则是 sum % 10。
逆序计算：
- 由于加法从个位开始进行，因此我们通常从字符串的右边开始加法，逐位向左。
- 为了处理进位以及构造结果，我们可以使用一个容器（如 string 或 vector）存储计算结果，最后将其逆序排列以得到正确的答案。

例题讲解

LC415 字符串相加

题目描述

给定两个字符串形式的非负整数 num1 和 num2，计算它们的和，并返回字符串形式的结果。你不能使用任何内建的大整数库（如 BigInteger），也不能直接将字符串转换为整数形式。

题目分析

要计算两个字符串形式的非负整数 num1 和 num2 的和，并返回结果为字符串形式，我们需要手动模拟加法的过程，类似于在纸上进行加法计算。下面是详细的解题思路和步骤。

解题思路

从右向左遍历：
- 由于加法是从个位开始的，因此我们需要从两个字符串的最右端逐位进行加法。
逐位相加：
- 对于 num1 和 num2 中的每一位，先将字符转化为数字进行加法操作。每位加法操作还需要考虑进位（carry）的影响。
处理不同长度的字符串：
- 如果两个字符串的长度不同，在遍历时处理较短字符串时，将缺失位默认为 0。
处理最后的进位：
- 如果遍历结束后进位不为 0，需要将进位加到最终结果中。
结果拼接与反转：
- 因为我们是从右向左进行计算，最后需要将结果反转后返回。

参考解答

C++
class Solution {
public:
    string addStrings(string num1, string num2) {
        int num1_index = num1.length() - 1;
        int num2_index = num2.length() - 1;
        string result = "";
        int carry = 0;

        // 从右到左逐位相加
        while (num1_index >= 0 || num2_index >= 0) {
            int total = carry;
            carry = 0;

            // 加上 num1 的当前位
            if (num1_index >= 0) {
                total += num1[num1_index] - '0';
                num1_index--;
            }

            // 加上 num2 的当前位
            if (num2_index >= 0) {
                total += num2[num2_index] - '0';
                num2_index--;
            }

            // 判断是否有进位
            if (total >= 10) {
                carry = 1;
            }

            // 当前位结果添加到字符串
            result.push_back(total % 10 + '0');
        }

        // 如果最后还有进位，添加到结果中
        if (carry == 1) {
            result.push_back(carry + '0');
        }

        // 结果是反向拼接的，需要反转
        reverse(result.begin(), result.end());

        return result;
    }
};

代码讲解

num1_index 和 num2_index：用来追踪两个字符串 num1 和 num2 的当前位。它们从字符串的最后一位开始，逐渐向前移动。
carry：用于处理进位。当某一位相加的结果大于等于 10 时，carry 设置为 1。
while (num1_index >= 0 || num2_index >= 0)：循环遍历两个字符串的每一位，直到所有位都被处理完。
result.push_back(total % 10 + '0')：将当前位的计算结果添加到结果字符串中。
反转结果：由于结果字符串是从低位到高位生成的，所以最后要使用 reverse 将其反转。

LC7 整数反转

题目描述

给定一个 32 位有符号整数 x，返回其数字部分反转后的结果。如果反转后的整数溢出（超出 32 位整数范围 [-2^31, 2^31 - 1]），则返回 0。

解题思路

处理数字的每一位：
- 我们从整数 x 的最后一位开始逐位提取数字，并将其加入到反转后的结果中。通过 x % 10 获取当前的最后一位，并使用 x / 10 移除最后一位。
反转构建：
- 每次提取一位数字后，将其加到结果的末尾，即将当前的 result 乘以 10 并加上提取的数字，从而逐步构建反转后的结果。
溢出检查：
- 在每次将数字加入 result 之前，需要检查 result 是否会超过 32 位整数的最大或最小范围。具体来说，如果 result 大于 INT_MAX / 10 或 result 等于 INT_MAX / 10 且当前数字大于 7，则结果会溢出，直接返回 0。同样的规则适用于最小值 INT_MIN。
返回结果：
- 当所有的位都处理完毕后，返回反转后的 result。如果 x 原本是负数，反转后结果仍然是负数。如果有溢出，则返回 0。

溢出条件说明

INT_MAX = 2147483647，最后一位是 7。
INT_MIN = -2147483648，最后一位是 -8。

参考解答

C++
class Solution {
public:
    int reverse(int x) {
        int result = 0;

        while (x != 0) {
            int digit = x % 10;

            // 检查是否会溢出：如果 result 超过了边界，返回 0
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
                return 0;
            }
            if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
                return 0;
            }

            // 构建反转后的结果
            result = result * 10 + digit;
            // 移除 x 的最后一位
            x /= 10;
        }

        return result;
    }
};

代码讲解

while (x != 0)：这个循环会处理输入整数 x 的每一位数字，直到 x 变为 0 为止。每次循环，都会提取 x 的最后一位数字并将其添加到结果中。
溢出检查：在更新 result 之前，检查是否可能发生溢出。具体是通过比较 result 和 INT_MAX / 10 或 INT_MIN / 10 来判断。如果 result 超过了 32 位整数的范围 (即大于 INT_MAX 或小于 INT_MIN)，则返回 0 以避免溢出。
digit = x % 10：这一行代码从 x 中提取最后一位数字（个位数）。例如，如果 x = 123，digit 会等于 3。
result = result * 10 + digit：这一步用于构建反转后的结果，将之前的 result 乘以 10 并加上提取的 digit，相当于将新的数字追加到结果的末尾。
x /= 10：通过将 x 除以 10 来移除最后一位数字，准备处理下一个数字。这样下一次循环就会处理剩余的数字。

举一反三

LC67 二进制求和

题目描述

给定两个二进制字符串 a 和 b，返回它们的和（以二进制字符串的形式）。

解题思路

从右到左遍历：
- 由于二进制加法从最低位开始，因此我们需要从两个字符串的最右端逐位进行相加。
逐位相加并处理进位：
- 使用两个指针分别指向两个字符串的最后一位，每一位相加时还需要考虑进位（carry）。
处理不同长度的字符串：
- 如果两个字符串长度不同，较短的字符串可能在某些位置缺失，需要在处理时将这些位置的值视为 0。
处理最后的进位：
- 如果遍历结束时仍有进位，则需要将进位添加到结果中。
拼接和反转结果：
- 因为加法是从右向左进行的，因此最终结果需要反转。

参考解答

C++
class Solution {
public:
    string addBinary(string a, string b) {
        int a_index = a.length() - 1;
        int b_index = b.length() - 1;
        int sum = 0;
        int carry = 0;
        string result = "";

        // 从右向左逐位相加
        while (a_index >= 0 || b_index >= 0) {
            sum = carry;  // 初始化 sum 为 carry
            carry = 0;  // 重置 carry

            // 取 a 的当前位
            if (a_index >= 0) {
                sum += a[a_index] - '0';
                a_index--;
            }

            // 取 b 的当前位
            if (b_index >= 0) {
                sum += b[b_index] - '0';
                b_index--;
            }

            // 计算是否需要进位
            if (sum >= 2) {
                carry = 1;
            }

            // 当前位的结果添加到字符串
            result.push_back(sum % 2 + '0');
        }

        // 如果有剩余的进位，添加到结果中
        if (carry == 1) {
            result.push_back(carry + '0');
        }

        // 结果是从右到左构建的，最后需要反转
        reverse(result.begin(), result.end());

        return result;
    }
};

代码讲解

while (a_index >= 0 || b_index >= 0)：使用两个指针从右向左遍历字符串 a 和 b。只要有一个字符串未遍历完，或者还有进位，就继续循环。
处理当前位的相加：
- 如果 a 还有未处理的位，就将该位的值加到 sum 中。同样的操作适用于 b。
- 处理每一位时，检查是否需要进位（sum >= 2），如果需要，则将 carry 设置为 1。
处理进位：
- 在每次相加后，更新 carry 并将结果的当前位（sum % 2）添加到结果字符串中。
最后的进位处理：
- 如果所有位处理完毕后仍有进位（carry == 1），则将 1 添加到结果字符串中。
反转结果：
- 因为加法是从右向左进行的，所以结果需要在最后进行反转。

LC989 数组形式的整数加法

题目描述

给定一个整数的数组形式 num 和一个整数 k，将这两个数相加并返回它们的和，结果以数组形式返回。num 是从左到右按位排列的整数。

解题思路

从右到左进行加法：
- 从数组 num 的最后一位（最低位）开始，与 k 的对应位相加。
处理进位：
- 每次相加可能产生进位，进位会影响下一次的计算。
遍历结束后处理剩余进位：
- 如果遍历 num 完毕，k 还有未处理的位，或者最后一次相加产生进位，需要将这些剩余位处理完。
结果构建：
- 因为加法从最低位开始，所以我们将计算结果存入一个向量 output，最后反转该向量得到正确的顺序。

参考解答

C++
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int num_index = num.size() - 1;
        vector<int> output;
        int carry = 0;

        // 从数组最后一位和k的末位开始逐位相加
        while (num_index >= 0 || k > 0) {
            int total = carry;  // 初始化 total 为 carry
            carry = 0;  // 重置 carry

            // 处理 num 的当前位
            if (num_index >= 0) {
                total += num[num_index];
                num_index--;
            }

            // 处理 k 的当前位
            if (k > 0) {
                total += k % 10;
                k /= 10;
            }

            // 判断是否有进位
            if (total >= 10) {
                carry = 1;
            }

            // 将当前位结果添加到输出
            output.push_back(total % 10);
        }

        // 如果有剩余的进位
        if (carry == 1) {
            output.push_back(carry);
        }

        // 由于我们是从低位开始构建结果，最终需要反转
        reverse(output.begin(), output.end());

        return output;
    }
};

代码讲解

while (num_index >= 0 || k > 0)：从数组 num 和整数 k 的末位开始，逐位相加，直到处理完所有位。
处理 num 和 k 当前位：
- 对于数组 num 的当前位，将其与 k 的当前位相加。如果 num 或 k 已经没有剩余位，则将其视为 0。
进位处理：
- 如果相加的总和 total 大于等于 10，则需要将 carry 置为 1，并且在下次循环中考虑进位。
将结果添加到 output：
- 每次相加的结果存储在 output 中，由于我们从低位开始相加，因此结果需要在最后进行反转。

课后练习

字符串循环+切片

题目编号	题目名称	简介
LC 1002	找到共同字符	找到给定字符串数组中所有字符串的共同字符。
LC 541	反转字符串 II	反转字符串中的指定部分，每隔一个指定长度反转一次。
LC 771	珠宝与石头	计算在石头中有多少个珠宝字符。
LC 844	回退字符串比较	比较两个字符串，考虑到回退字符（‘#’）的影响。
LC 925	长按键入的名字	检查一个名字是否可以通过长按另一个名字的字符来实现。

字符串数学运算

题目编号	题目名称	简介
LC 2243	计算字符串中的数字和	计算字符串中所有数字字符的总和。
LC 66	加一	在数组形式的数字上加一，并返回结果的数组形式。

Lesson8 字符串循环+切片/字符串数学运算专题

目录

1. 字符串循环+切片

例题讲解

LC14 最长公共前缀

题目分析

思路

参考解答

LC125. 验证回文串

问题描述

题目分析

思路

具体步骤

参考解答

代码详解

举一反三

LC459. 重复的子字符串

问题描述

解题思路

参考解答

详细讲解

更高效的解法

优化示例代码

证明：字符串拼接后掐头去尾可以用于判断重复的子字符串

补充：什么是前缀和后缀？

充分必要性证明

1. 充分性

2. 必要性

总结：

补充材料：

LC796 旋转字符串

问题描述

解题思路

示例代码

代码讲解

LC28 查找字符串中的第一个匹配项索引

问题描述

思路分析

参考解答

2. 字符串数学运算

基本概念

例题讲解

LC415 字符串相加

题目描述

题目分析

解题思路

参考解答

代码讲解

LC7 整数反转

题目描述

解题思路

溢出条件说明

参考解答

代码讲解

举一反三

LC67 二进制求和

题目描述

解题思路

参考解答

代码讲解

LC989 数组形式的整数加法

题目描述

解题思路

参考解答

代码讲解

课后练习

字符串循环+切片

字符串数学运算