代码随想录算法训练营二十四期第九天

二十四期第九天"/>

代码随想录算法训练营二十四期第九天

一、LeetCode28. 找出字符串中第一个匹配项的下标

题目链接：28. 找出字符串中第一个匹配项的下标
解法一：
我们可以用双重for循环去一次比较第一个字符串的子串与第二个字符串。时间复杂度是O(n^2)
代码如下：

class Solution {public int strStr(String haystack, String needle) {for(int i = 0; i <= haystack.length() - needle.length(); i++) {if(haystack.charAt(i) == needle.charAt(0)) {int j = i;for(int k = 0; k < needle.length(); k++) {if(haystack.charAt(j++) != needle.charAt(k)) {break;}else if(k == needle.length() - 1) {return i;}}}}return -1;}
}

解法二（KMP算法）：
先通过模式串创建前缀表，（1、初始化；2、处理前后缀不想同情况；3、处理前后缀相同情况）；
根据前缀表去寻找主串中是否有模式串。
代码如下：

class Solution {int[] getNext(int[] next, String s) {//创建前缀表int j = 0;next[0] = j;for(int i = 1; i < s.length(); i++) {while(j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if(s.charAt(i) == s.charAt(j)) j++;next[i] = j;}return next;}public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];next = getNext(next, needle);int j = 0;for(int i = 0; i < haystack.length(); i++) {while(j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];if(haystack.charAt(i) == needle.charAt(j)) j++;if(j == needle.length()) return i - j + 1;}return -1;}
}

时间复杂度O(n)

二、LeetCode459. 重复的子字符串

题目链接：459. 重复的子字符串
KMP算法：
创建前缀表，求出最长想通前后缀长度len，如果len大于0并且(s.length() % (s.length()-len)==0)，说明该字符串可以由一些长度为s.length() - len的子串重复构成。
具体分析请看卡哥的PPT解析

class Solution {int[] getNext(int[] next, String s) {int j = 0;next[0] = 0;for(int i = 1; i < s.length(); i++) {while(j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if(s.charAt(i) == s.charAt(j)) j++;next[i] = j;}return next;}public boolean repeatedSubstringPattern(String s) {int[] next = new int[s.length()];next = getNext(next, s);if(next[s.length() - 1] > 0 &&s.length() % (s.length() - next[s.length() - 1]) == 0) return true;return false;}
}

时间复杂度O(n)，空间复杂度O(n)

总结

初步了解KMP算法