Skip to content

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

目录

  1. 字符串循环+切片

  2. 字符串数学运算

  3. 课后练习

1 字符串循环+切片

例题讲解

LC14 最长公共前缀

题目描述

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

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

题目分析

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

解题思路

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

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 边界情况处理
        if not strs:
            return ""
        # 初始化最长公共前缀为第一个字符串
        prefix = strs[0]

        # 依次与其他字符串比较
        for i in range(1, len(strs)):
            # 当前前缀与下一个字符串比较
            while strs[i].find(prefix) != 0:
                # 缩短前缀长度
                prefix = prefix[:len(prefix) - 1]
                # 如果前缀为空，返回空字符串
                if not prefix:
                    return ""

        return prefix

LC125. 验证回文串

问题描述

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

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

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

题目分析

我们需要统计字符串中的单词个数，单词是由连续的非空格字符组成的。空格可以用来分隔单词。题目保证字符串中没有不可打印字符，因此不需要处理特殊字符。

解题思路

对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。

可以使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def isPalindrome(self, s: str) -> bool:
        sgood = []  # 用于存储有效字符
        for ch in s:
            if ch.isalnum():  # 判断是否为字母或数字
                sgood.append(ch.lower())  # 转为小写并添加到有效字符中

        # 创建反转后的有效字符字符串
        sgood_rev = sgood[::-1]  # 反转列表

        # 比较有效字符和反转字符是否相同
        return sgood == sgood_rev

举一反三

LC459. 重复的子字符串

问题描述

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

解题思路

  1. 理解重复构成：

    • 如果字符串 s 可以通过重复某个子串多次构成，说明 s 的长度应该是这个子串的长度的整数倍。
    • 例如，字符串 "abab" 可以视为子串 "ab" 重复两次，长度为 4 的字符串可由长度为 2 的子串构成。

  2. 找到可能的子串长度：

    • 假设子串的长度为 n，则可能的长度可以是 1 到 len(s) // 2。因为一个子串重复后，整体字符串的长度不可能超过 len(s)。

  3. 检查重复：

    • 对于每一个可能的子串长度 i，检查 len(s) 是否能够被 i 整除（即 len(s) % i == 0）。
    • 如果能整除，那么取出子串 s[0:i]，并通过将其重复 len(s) // i 次来构造一个新的字符串，然后与原字符串 s 进行比较。

  4. 复杂度分析：

    • 在最坏的情况下，外层循环需要检查 len(s) // 2 次，每次比较的复杂度为 O(n)。所以总体的时间复杂度为 O(n^2)，对于 n 较大时可能会有性能问题。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)   
        # 遍历可能的子串长度
        for i in range(1, n // 2 + 1):
            # 检查是否可以整除
            if n % i == 0:
                substring = s[:i]
                # 构造由子串重复的字符串
                repeated = substring * (n // i)
                # 比较构造的字符串与原字符串
                if repeated == s:
                    return True

        return False

更高效的解法

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

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

优化示例代码

Python
1
2
3
4
5
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        doubled = s + s  # 将字符串拼接
        sub_string = doubled[1:-1]  # 去掉首尾字符
        return s in sub_string  # 检查是否包含原字符串

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

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

  1. 前缀（Prefix）：从字符串的开头开始的连续字符子串。例如，字符串 "abcde" 的前缀有：

    • 前缀 1："a"
    • 前缀 2："ab"
    • 前缀 3："abc"
    • 前缀 4："abcd"
    • 前缀 5："abcde"（整个字符串本身也是一个前缀）

  2. 后缀（Suffix）：从字符串的结尾开始的连续字符子串。例如，字符串 "abcde" 的后缀有：

    • 后缀 1："e"
    • 后缀 2："de"
    • 后缀 3："cde"
    • 后缀 4："bcde"
    • 后缀 5："abcde"（整个字符串本身也是一个后缀）

充分必要性证明

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

  1. 充分性：如果一个字符串 s 是由某个子串重复构成的，那么在拼接后的字符串 s + s 中，掐头去尾后，一定能再次找到 s。
  2. 必要性：如果在掐头去尾的 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
2
s = "abab"
s_plus = s + s  # "abab" + "abab" = "abababab"

接着，掐头去尾，去掉首尾字符，得到 new_s = (s + s)[1:-1]，对于上面的例子：

Text Only
1
2
new_s = s_plus[1:-1]  # 去掉首尾字符
# new_s = "abababab"[1:-1] = "bababa"

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

Text Only
1
2
3
new_s = "bababa"
          ↓↓↓↓
         "abab"  # 这里再次出现了 s

充分性证毕。

2. 必要性

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

构造 new_s：首先，构造

Text Only
1
2
s_plus = s + s
new_s = s_plus[1:-1]  # 去掉首尾字符

假设 s 在 new_s 中匹配的位置是从索引 i 开始，这意味着：

Text Only
1
new_s[i:i+len(s)] == s

由于 new_s 是 s + s 去掉首尾字符得到的，即：

Text Only
1
new_s = s_plus[1:-1] = (s + s)[1:-1]

所以：

Text Only
1
new_s = s[1:] + s[:-1]

因此，new_s 是由 s 的后缀和前缀拼接而成。

根据匹配条件：

Text Only
1
s == new_s[i:i+len(s)]

即：

Text Only
1
s == (s[1:] + s[:-1])[i:i+len(s)]

这表明 s 可以通过自身的一个后缀和前缀拼接得到，说明 s 存在周期性，也就是说，s 是由某个子串重复构成的。

举例说明：

Text Only
1
2
3
s = "abab"
s_plus = s + s  # "abababab"
new_s = s_plus[1:-1]  # "bababa"
Text Only
1
2
- `s` 的前缀有：`'a', 'ab', 'aba', 'abab'`
- `s` 的后缀有：`'b', 'ab', 'bab', 'abab'`

可以发现，在 new_s 中，s 再次出现：

Text Only
1
new_s[1:1+4] == "abab"  # "bababa"[1:5] == "abab"

这说明：

  • s 的后缀 "bab" 与前缀 "ab" 重叠拼接，形成了周期性。
  • 因此，s 是由 "ab" 重复构成的。

换句话说，如果 s 的前缀和后缀有某种重叠，形成了周期性，那么 s 就可以通过重复某个子串构成。

必要性证毕。

总结：

我们已经证明了：

  1. 充分性：如果 s 是由某个子串重复构成的，那么在 s + s 中掐头去尾后，一定能够再次找到 s。这是因为重复子串会使得前缀和后缀有重叠。

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

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

补充材料：

充分性及必要性证明

Leetcode官方题解证明

LC796 旋转字符串

问题描述

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

要判断字符串 s 是否可以通过若干次旋转操作变成字符串 goal，我们可以采用以下思路进行解决：

解题思路

  1. 理解旋转：

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

  2. 字符串旋转的特性：

    • 如果我们将字符串 s 进行两次拼接，得到 s + s，这个新字符串包含了所有可能的旋转形式。
    • 例如：
    • 对于 s = "abcde"，拼接后 s + s = "abcdeabcde"，其中包含了 "abcde" 的所有旋转形式，如 "abcde"、"bcdea"、"cdeab"、"deabc" 和 "eabcd"。

  3. 判断 goal 是否在 s + s 中：

    • 只需检查 goal 是否是 s + s 的子串。
    • 如果 goal 是 s + s 的子串，则返回 True，否则返回 False。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        # 检查长度是否相等
        if len(s) != len(goal):
            return False

        # 拼接字符串
        doubled = s + s

        # 检查 goal 是否为 doubled 的子串
        return goal in doubled

简洁写法

Python
1
2
3
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in (s + s)

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

问题描述

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

思路分析

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

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 如果needle为空字符串，直接返回0
        if not needle:
            return 0

        # 获取两个字符串的长度
        n = len(haystack)
        m = len(needle)

        # 遍历haystack，直到剩余的部分长度小于needle长度
        for i in range(n - m + 1):
            # 比较从i开始的子串是否等于needle
            if haystack[i:i + m] == needle:
                return i

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

2 字符串数学运算

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

基本概念

  1. 字符转数字：

    • 字符串中的数字是以字符的形式存在的，例如字符 '0' 到 '9'。
    • 可以通过 ord(char) - ord('0') 将字符转为对应的数字。例如，ord('5') - ord('0') 的结果为 5。

  2. 进位处理：

    • 在进行加法运算时，如果某一位的和大于或等于 10，则需要处理进位（carry），将 1 加到下一位的计算中。
    • 进位的计算可以通过 carry = sum // 10 来实现，而当前位的结果则是 sum % 10。

  3. 逆序计算：

    • 字符串通常从右到左进行加法，因为我们从个位开始。处理完最后一位后，继续处理十位、百位等。
    • 为了方便存储结果，通常会使用列表逐位添加，最后通过 ''.join(list) 以获得正确的顺序的字符串。

例题讲解

LC415 字符串相加

问题描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

题目分析

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

解题思路

  1. 从右到左遍历：

    • 加法通常是从个位开始计算，因此我们需要从两个字符串的末尾开始遍历。

  2. 逐位相加：

    • 对于 num1 和 num2 中的每一位，分别将它们转化为数字，进行加法操作。
    • 需要考虑进位（carry）的影响，即如果某一位的和大于或等于 10，则需要将 1 进位到下一位。

  3. 处理不同长度的字符串：

    • 在进行加法时，如果两个字符串的长度不同，我们需要确保从最右边开始添加上短字符串的缺失部分。
    • 例如，对于 num1 长度为 5 和 num2 长度为 3 的情况，我们只需要在计算时考虑 num2 的前三位。

  4. 处理最后的进位：

    • 如果遍历结束后还有进位（carry）未处理，需要将其添加到结果中。

  5. 结果拼接：

    • 由于我们是从后向前计算的，因此最终的结果需要反转一下。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        result = []  # 使用列表存储结果
        carry = 0  # 进位
        i, j = len(num1) - 1, len(num2) - 1  # num1 和 num2 的最后一位索引

        # 循环直到 num1 和 num2 都遍历完
        while i >= 0 or j >= 0 or carry > 0:
            sum = carry  # 从进位开始
            if i >= 0:
                sum += int(num1[i])
                i -= 1  # 移动到上一位
            if j >= 0:
                sum += int(num2[j])
                j -= 1  # 移动到上一位

            result.append(str(sum % 10))  # 当前位的结果
            carry = sum // 10  # 更新进位

        return ''.join(result[::-1])  # 反转结果并返回

LC7 整数反转

问题描述

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

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

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

解题思路

我们需要逐位反转整数 x，并在过程中检查是否会发生溢出。以下是具体步骤：

  1. 初始化变量：
    • result = 0：用于存储反转后的结果。
    • sign = -1 if x < 0 else 1：记录 x 的符号，负数为 -1，非负数为 1。
    • x = abs(x)：对 x 取绝对值，方便后续处理。
  2. 定义整数范围：
    • INT_MAX = 2**31 - 1：32 位有符号整数的最大值，即 2147483647。
    • INT_MIN = -2**31：32 位有符号整数的最小值，即 -2147483648。
  3. 循环反转数字：

当 x 不等于 0 时，重复以下步骤：

  • 提取最后一位数字：digit = x % 10。
  • 移除最后一位数字：x = x // 10。

4.优化后的溢出检查：

在将 digit 加入 result 之前，检查是否会溢出。

如果 result > INT_MAX // 10，则乘以 10 后一定会溢出，返回 0

如果 result == INT_MAX // 10，需要根据 digit 进一步判断：

  • 如果 digit > INT_MAX % 10（即 7），则会溢出，返回 0。

5.更新结果：

  • 将提取的数字加入结果中：result = result * 10 + digit。

6.恢复符号并返回结果：

  • 返回最终结果：return result * sign。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX = 2**31 - 1  # 2147483647
        INT_MIN = -2**31     # -2147483648

        sign = -1 if x < 0 else 1  # 记录符号
        x = abs(x)
        result = 0

        while x != 0:
            digit = x % 10
            x = x // 10

            # 溢出检查
            if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > INT_MAX % 10):
                return 0

            result = result * 10 + digit

        return sign * result

溢出检查条件说明

条件一：result > INT_MAX // 10

  • 如果 result 大于 214748364，那么下一次 result * 10 后一定会超过 2147483640，加上任何 digit 都会溢出。

条件二：result == INT_MAX // 10 and digit > INT_MAX % 10

  • 如果 result 等于 214748364，需要检查 digit 是否大于 7（INT_MAX % 10）。
  • 因为 INT_MAX 的个位是 7，如果 digit > 7，则反转后会超过 INT_MAX，发生溢出。

举一反三

LC67 二进制求和

问题描述

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

解题思路

  1. 从右到左遍历：

    • 由于二进制加法是从最右侧的位（最低位）开始的，我们需要从字符串的末尾开始处理。

  2. 逐位相加：

    • 使用两个指针分别指向两个字符串的末尾（即最后一位）。
    • 逐位相加并处理进位（carry）。

  3. 处理不同长度的字符串：

    • 如果两个字符串的长度不同，短的字符串在计算时会缺失部分位。需要在处理过程中检查是否已经超出某个字符串的长度。

  4. 处理最后的进位：

    • 如果遍历结束后仍然有进位（carry），需要将其添加到结果中。

  5. 拼接和反转结果：

    • 由于我们是从后向前计算的，因此需要在最后反转结果字符串。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []  # 使用列表存储结果
        carry = 0  # 进位
        i, j = len(a) - 1, len(b) - 1  # a 和 b 的最后一位索引

        # 循环直到 a 和 b 都遍历完
        while i >= 0 or j >= 0 or carry > 0:
            # 计算当前位的和
            if i >= 0:
                carry += int(a[i])  # 取 a 的当前位并转为数字
                i -= 1
            if j >= 0:
                carry += int(b[j])  # 取 b 的当前位并转为数字
                j -= 1

            # 将当前位的结果添加到结果中
            result.append(str(carry % 2))  # 当前位结果
            carry //= 2  # 更新进位

        return ''.join(result[::-1])  # 反转结果并返回

LC989 数组形式的整数加法

问题描述

整数的数组形式 num 是按照从左到右的顺序表示其数字的数组。

例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。 给定 num ，整数的数组形式，和整数 k ，返回 整数 num + k 的数组形式。

解题思路

  1. 从右到左进行加法：

    • 从数组 num 的最后一位（最低位）开始加，逐位处理。

  2. 处理进位：

    • 每一位的和可能会产生一个进位，我们需要记录这个进位并在下一位的加法中使用。

  3. 遍历结束后的处理：

    • 如果在遍历结束时仍有进位，需要将进位添加到结果中。

  4. 结果构建：

    • 将计算的结果存储在一个列表中，最后需要反转这个列表，因为我们是从最低位开始计算的。

示例代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        result = []  # 用于存放结果的列表
        carry = 0  # 初始化进位
        n = len(num)  # 数组长度

        # 从数组的最后一位开始处理
        for i in range(n - 1, -1, -1):
            sum = num[i] + (k % 10) + carry  # 当前位的和
            result.append(sum % 10)  # 当前位结果
            carry = sum // 10  # 更新进位
            k //= 10  # 移动到 k 的下一位

        # 处理 k 可能还有的剩余位
        while k > 0 or carry > 0:
            sum = (k % 10) + carry  # 当前位的和
            result.append(sum % 10)  # 当前位结果
            carry = sum // 10  # 更新进位
            k //= 10  # 移动到 k 的下一位

        # 由于我们是从后向前构建的结果，需要反转
        return result[::-1]  # 反转结果并返回

课后练习

字符串循环+切片

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

字符串数学运算

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