字符串

实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在，则返回 -1。

方法一：暴力

public int strStr(String haystack, String needle) {
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        boolean flag = true;
        for (int j = 0; j < needle.length(); j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                flag = false;
                break;
            }
        }
        if (flag)  {
            return i;
        }
    }
    return -1;
}

时间复杂度：O(m*n)

方法二：KMP

public int strStr(String haystack, String needle) {
    int m = haystack.length(), n = needle.length();
    if (n == 0) {
        return 0;
    }
    int[] next = next(needle);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else if (j == 0) {
            i++;
        } else {
            j = next[j - 1] + 1;
        }
    }
    return j == n ? i - n : -1;
}

private int[] next(String s) {
    int[] res = new int[s.length()];
    res[0] = -1; 
    for (int i = 1; i < s.length(); i++) {
        int j = res[i - 1];
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = res[j];
        }
        if (s.charAt(i) == s.charAt(j + 1)) {
            res[i] = j + 1;
        } else {
            res[i] = -1;
        }
    }
    return res;
}

时间复杂度：O(m+n)

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]输出：["h","a","n","n","a","H"]

public void reverseString(char[] s) {
    int i = 0, j = s.length - 1;
    while (i < j) {
        char tmp = s[i];
        s[i++] = s[j];
        s[j--] = tmp;
    }
}

反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2输出："bacd"

我的：

public String reverseStr(String s, int k) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        int spilt = i + k - 1;
        if (spilt >= s.length()) {
            spilt = s.length() - 1;
        }
        int j = spilt;
        while (j >= i) {
            sb.append(s.charAt(j--));
        }
        j = spilt + 1;
        while (j <= spilt + k && j < s.length()) {
            sb.append(s.charAt(j++));
        }
        i += 2 * k;
    }
    return sb.toString();
}

转数组：

public String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i += k * 2) {
        reverse(chars, i, Math.min(chars.length - 1, i + k - 1));
    }
    return new String(chars);
}

private void reverse(char[] chars, int left, int right) {
    while (left < right) {
        char tmp = chars[left];
        chars[left++] = chars[right];
        chars[right--] = tmp;
    }
}

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"输出: true解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"输出: false

示例 3:

输入: s = "abcabcabcabc"输出: true解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

方法一：枚举
从头开始，将已遍历的串认为是可能的子串，依次向后比较

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    // 子串为s[0, i - 1]
    for (int i = 1; i * 2 <= n; i++) {
        // 整除才有可能
        if (n % i == 0) {
            boolean match = true;
            for (int j = i; j < n; j++) {
                // i就是子串的长度，-i就是上一次出现的位置
                if (s.charAt(j) != s.charAt(j - i)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
    }
    return false;
}

时间复杂度：O(n²)

方法二：字符串匹配
如果字符串 S 包含一个重复的子字符串，意味着可以多次 “移位和换行”`您的字符串，并使其与原始字符串匹配。

例如：abcabc
移位一次：bcabca
移位两次：cabcab
移位三次：abcabc
现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串。
基于这个思想，可以每次移动k个字符，直到匹配移动 length / 2次。但是这样对于重复字符串很长的字符串，效率会非常低。

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    for (int i = 0; i < s.length() / 2; i++) {
        String sub = s.substring(0, i + 1);
        if (s.equals(s.substring(i + 1) + sub)) {
            return true;
        }
    }
    return false;
}

为了避免这种无用的环绕，可以创建一个新的字符串 str，它等于原来的字符串 S 再加上 S 自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么 str = S + S = acdacd

acd 移动的可能：cda、dac。其实都包含在了 str 中了

一开始 acd (acd) ，移动一次 a(cda)cd，移动两次 ac(dac)d。循环结束

所以可以直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串

public boolean repeatedSubstringPattern(String s) {
    return (s + s).indexOf(s, 1) != s.length();
}

方法三：KMP
利用next数组特点

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    if (n == 0) {
        return false;
    }
    int[] next = next(s);
    // (n- (next[n- 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串(asdf)
    if (next[n - 1] >= 0 && n % (n - next[n - 1] - 1) == 0) {
        return true;
    }
    return false;
}

private int[] next(String s) {
    int[] res = new int[s.length()];
    res[0] = -1; 
    for (int i = 1; i < s.length(); i++) {
        int j = res[i - 1];
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = res[j];
        }
        if (s.charAt(i) == s.charAt(j + 1)) {
            res[i] = j + 1;
        } else {
            res[i] = -1;
        }
    }
    return res;
}