Leetcode 459.重复的子字符串

题目：459.重复的子字符串

初始思路

如果可以由子串构成的话，重复次数至少为2，那么前后一定是相同的。感觉跟KMP算法的最长相等前缀有类似的地方。

代码

  1. // 常规解法
  2. var repeatedSubstringPattern = function (s) {
  3.     // 1. 设置 s 的长度 length
  4.     const length = s.length;
  6.     if (length === 0) return false
  8.     // 2. 设置每次累加的长度
  9.     let str = '';
  11.     // 3. 遍历字符串 子串可能不会超过原字符串的一半
  12.     for (let i = 0; i < Math.floor(length / 2); i++) {
  13.         // 3.1 累加字符串
  14.         str += s[i];
  15.         // 3.2 判断是否为重复的长度
  16.         // 使用了ES6的一个函数
  17.         if (s === str.repeat(Math.floor(length / str.length))) {
  18.             return true;
  19.         }
  20.     }
  22.     // 4. 如果不存在，则返回 false
  23.     return false;
  24. };
  1. // KMP解法
  2. var repeatedSubstringPattern = function (s) {
  3.     if (s.length === 0)
  4.         return false;
  6.     const getNext = (s) => {
  7.         let next = [];
  8.         let j = 0;
  10.         next.push(j);
  12.         for (let i = 1; i < s.length; ++i) {
  13.             while (j > 0 && s[i] !== s[j])
  14.                 j = next[j - 1];
  15.             if (s[i] === s[j])
  16.                 j++;
  17.             next.push(j);
  18.         }
  20.         return next;
  21.     }
  23.     let next = getNext(s);
  25.     if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0)
  26.         return true;
  27.     return false;
  28. };

感想

  1. 常规解法能看懂，KMP解法还是没明白。。。二刷再说

  2. 使用了ES6的repeat函数

    字符串总结

  3. 双指针法在数组，链表和字符串中很常用。

  4. 数组填充类的问题，都可以先预先给数组扩容到填充后的大小，然后从后往前进行操作。
  5. 反转字符串是一个很常见的题目，需要牢记。
  6. KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。没怎么看懂，二刷再说。