代码随想录算法训练营day9 | 题目28、题目459
题目一描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 10^4
haystack 和 needle 仅由小写英文字符组成
解题思路
可以暴力匹配子串
可以KMP，暂时死记硬背下来了，感觉在构建Next数组的时候，也用到了回退上一个状态这样的技巧或者思想，这个算法还需要逐字逐句去理解
构建next的四步：
1，初始化next数组（next[0]=0），第一个字符不能再回退了。
2，处理字符不同的情况（while循环，回退到字符与目前字符相同，直到回到下标为0）
3，处理字符相同的情况（相同就j++）
4，更新next数组
代码实现
方法一：
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()>haystack.length())
return -1;
for(int i = 0; i < haystack.length(); i++){
if(i + needle.length() > haystack.length())
break;
if(haystack.charAt(i) == needle.charAt(0)){
if(haystack.substring(i, i+needle.length()).equals(needle)){
return i;
}
}
}
return -1;
}
}
方法二：
class Solution {
public int strStr(String haystack, String needle) {
int[] next = new int[needle.length()];
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 - needle.length() + 1;
}
}
return -1;
}
public void 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;
}
}
}
技巧总结
背下来KMP求next数组的模板
题目二描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 10^4
s 由小写英文字母组成
解题思路
先暴力，找出每一种子串，挨个遍历匹配
思路二，s和s相加，然后去掉首字母和尾字母，如果这个新的字符串里能够找到原字符串s，说明s由子串重复构成。使用库函数
思路三，同上，不过使用KMP
代码实现
方法一：
class Solution {
public boolean repeatedSubstringPattern(String s) {
for (int l = 1; l <= s.length() / 2; l++) {
int start = 0;
int end = start + l;
if (s.length() % l != 0) {
continue;
}
String subStr = s.substring(start, end);
boolean thisSub = true;
while (start < s.length()) {
if (s.substring(start, end).equals(subStr)) {
start = end;
end = start + l;
} else {
thisSub = false;
break;
}
}
if(thisSub)
return true;
}
return false;
}
}
方法二：
class Solution {
public boolean repeatedSubstringPattern(String s) {
String newS = (s + s).substring(1, s.length() * 2 - 1);
if (newS.indexOf(s) != -1) {
return true;
}
return false;
}
}
方法三：
class Solution {
public boolean repeatedSubstringPattern(String s) {
String newS = (s + s).substring(1, s.length() * 2 - 1);
int[] next = new int[s.length()];
getNext(next, s);
int j = 0;
for (int i = 0; i < newS.length(); i++) {
while (j > 0 && s.charAt(j) != newS.charAt(i)) {
j = next[j - 1];
}
if (s.charAt(j) == newS.charAt(i)) {
j++;
}
if (j == s.length()) {
return true;
}
}
return false;
}
private void 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;
}
}
}
技巧总结
字符串重复加自己的操作，值得记住
