【Python3】巧用空格和KMP中的next数组解决力扣459.重复字符串

思路

1. 核心问题

判断一个字符串 s 是否由某个子串重复多次构成（即 s = substr * k, k ≥ 2）。

2. 整体策略

利用 KMP 算法的前缀函数（next 数组），求出整个字符串的 最长相等前后缀长度，然后通过数学关系判断是否能由重复子串组成。

3. 代码分步解析

（1）边界处理

• 若字符串为空，直接返回 False（空串不视为由重复子串构成）。

（2）添加哨兵空格（巧妙之处①）

• 在原字符串前加一个空格字符，变为 " " + s。
• 目的：使有效字符的下标从 1 开始，便于后续 KMP 处理，同时避免单独初始化 next[0]，让代码更统一。

（3）构建 next 数组（前缀函数）

• 数组长度 n + 1（下标 0 不使用，next[i] 表示子串 chars[1..i] 的最长相等前后缀长度）。
• 初始化 j = 0（代表当前已匹配的前缀长度）。
• 从 i = 2 遍历到 n（因为 chars[1] 是第一个有效字符，无需计算前后缀）。
• 核心循环：
  • 回退机制（巧妙之处②）：当 j > 0 且当前字符 chars[i] 与 chars[j+1] 不匹配时，不断将 j 回退到 next[j]，利用已计算的前缀信息快速寻找更短的可匹配前缀。
  • 匹配成功时 j 自增。
  • 将 j 存入 next[i]。

（4）利用 next 数组判断重复性（关键结论）

• 若 next[n] > 0（存在非空前缀和后缀相等），且满足 n % (n - next[n]) == 0，则返回 True。
• 数学原理：
  • 令 len = n - next[n]，len 代表 最小重复子串的长度（如果存在）。
  • 因为整个字符串的最长相等前后缀长度是 next[n]，那么剩余部分 n - next[n] 就是最小重复单元的长度。
  • 只有当 n 能被 len 整除 时，字符串才完全由该子串重复构成。

4. 复杂度

• 时间复杂度：O(n)（KMP 前缀函数构建为线性）
• 空间复杂度：O(n)（存储 next 数组）

详细代码

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # 判断字符串是否为空，为空则返回false
        if not s:
            return False
        
        # 给原字符串添加空格，让下标从1开始
        chars = ' ' + s
        n = len(s)
        next_arr=[0]*(n+1)

        # 构造next数组
        j = 0
        for i in range(2, n+1):
            while j > 0 and chars[i] != chars[j + 1]:
                j = next_arr[j]
            if chars[i] == chars[j + 1]:
                j += 1
            next_arr[i] = j
        
        if next_arr[n] > 0 and n % (n - next_arr[n]) == 0:
            return True

        return False

提交结果

通过