LeetCode-459.重复的子字符串

发表于 | 分类于 | 热度 ℃
| 本文字数 4.6k | 阅读时长 ≈ 4 分钟

题目详解

相关链接

思路

  • 想到了用KMP，但是没想明白前缀表的用处

看完代码随想录之后的想法

  • get了移动字符串匹配解法
  • 利用前缀表 通过数学推导出最小重复子串：除去最大公共前后缀的剩余部分就是最小重复子串

实现过程中遇到的困难

  • KMP求前缀表
  • 前缀表的作用

代码

  • 移动字符串匹配

    TypeScript
    1
    2
    3
    function repeatedSubstringPattern(s: string): boolean {
      return (s + s).slice(1, s.length * 2 - 1).includes(s)
    }

  • KMP

    TypeScript
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function repeatedSubstringPattern(s: string): boolean {
      const prefix = getPrefix(s),
        lastPrefix = prefix[prefix.length - 1]
      return lastPrefix !== 0 && (s.length % (s.length - lastPrefix)) === 0
    }

    function getPrefix(s: string): number[] {
      let j = 0
      const prefix: number[] = [j]
      for (let i = 1; i < s.length; i++) {
        while (j > 0 && s[i] !== s[j]) j = prefix[j - 1]
        if (s[i] === s[j]) j++
        prefix[i] = j
      }
      return prefix
    }

收获

  • get了利用KMP求最小重复子串的方法
相关文章
-------- 本文结束 感谢阅读 --------
0%