代码随想录算法训练营day9 | 题目28、题目459

题目一描述

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

给你两个字符串 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数组的模板

题目二描述

459. 重复的子字符串

给定一个非空的字符串 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;
        }
    }
}

技巧总结

字符串重复加自己的操作，值得记住