字符串Tag

字符串
字符串类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。
双指针法是字符串处理的常客。
KMP 算法是字符串查找最重要的算法，要知道怎么获取 next 数组，并且如何使用它。

字符串

1.反转字符串

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1：
1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
提示：
- 1 <= s.length <= 105
- s[i] 都是 ASCII 码表中的可打印字符

思路

没啥好说的，用一个临时变量辅助对两个值进行互换。

class Solution {
    public void reverseString(char[] s) {
        char c;
        for (int i = 0; i < s.length / 2; i++) {
            c = s[i];
            s[i] = s[s.length - i - 1];
            s[s.length - i - 1] = c;
        }
    }
}

2.反转字符串II

题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
1
2
输入：s = "abcd", k = 2
输出："bacd"
提示：
- 1 <= s.length <= 104
- s 仅由小写英文组成
- 1 <= k <= 104

思路

在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

class Solution {
    public String reverseStr(String s, int k) {
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i += 2 * k) {
            int start = i;
            int end = Math.min(charArray.length - 1, start + k - 1);
            while (start < end) {
                char c;
                c = charArray[start];
                charArray[start] = charArray[end];
                charArray[end] = c;
                start++;
                end--;
            }
        }
        return new String(charArray);
    }
}

3.翻转字符串里的单词

题目

给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
1
2
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
1
2
3
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
1
2
3
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
- 1 <= s.length <= 104
- s 包含英文大小写字母、数字和空格 ' '
- s 中 至少存在一个 单词

思路

如果用现有的库函数的话，这题其实很简单：

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        s = s.trim(); // 处理两头的空格
        String[] array = s.split("\\s+"); // 单词分割
        for (int i = array.length - 1; i >= 0; i--) {
            sb.append(array[i]);
            if (i > 0) {
                sb.append(' ');
            }
        }
        return sb.toString();
    }
}

进阶：不要使用现有的 trim 和 split 函数，自己完成具体的细节。

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        List<String> list;
        s = trimSpace(s);
        list = splitString(s);
        while (!list.isEmpty()) {
            String word = list.remove(list.size() - 1);
            sb.append(word);
            if (!list.isEmpty()) {
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    // 移除两端的空格
    public String trimSpace(String s) {
        int left, right;
        left = 0;
        right = s.length() - 1;
        while (s.charAt(left) == ' ') {
            left++;
        }
        while (s.charAt(right) == ' ') {
            right--;
        }
        return s.substring(left, right + 1);
    }

    // 提取出空格分隔的单词
    public List<String> splitString(String s) {
        List<String> list = new ArrayList<>();
        int start, end;
        start = end = 0;
        while (start < s.length()) {
            while (s.charAt(end) != ' ') {
                end++;
                if (end == s.length()) {
                    break;
                }
            }
            String word = s.substring(start, end);
            list.add(word);
            if (end == s.length()) {
                break;
            }
            while (s.charAt(end) == ' ') {
                end++;
                // 因为已经移除两端的空格了，所以不需要下面的判断
                // if (end == s.length()) {
                //     break;
                // }
            }
            start = end;
        }
        return list;
    }
}

实际做题还是优先用库函数。

4.★实现strStr(KMP)

题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
- 1 <= haystack.length, needle.length <= 104
- haystack 和 needle 仅由小写英文字符组成

思路

对于判断是否是子串的问题，很明显是用 KMP 算法来做。
- KMP 的经典思想就是：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
写过 KMP 的同学，一定都写过 next 数组，那么这个 next 数组究竟是个啥呢？
- next 数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
- 首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，应该跳到哪个位置，再进行模式串匹配。

所以 KMP 算法分为两步：

获得 next 数组。
使用 next 数组进行匹配。

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = getNext(needle);
        int i, j;
        i = j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1] + 1;
            } else {
                i++;	// 说明模式串的第一个字符就没匹配，所以文本串的下标向后移动一位
            }
        }
        return j == needle.length() ? (i - j) : -1;
    }

    // 获取模式串的next数组
    public int[] getNext(String needle) {
        int[] next = new int[needle.length()];
        next[0] = -1;
        for (int i = 1; i < needle.length(); i++) {
            int temp = next[i - 1];
            while (temp >= 0 && needle.charAt(temp + 1) != needle.charAt(i)) {
                temp = next[temp];
            }
            if (needle.charAt(temp + 1) == needle.charAt(i)) {
                next[i] = temp + 1;
            } else {
                next[i] = -1;
            }
        }
        return next;
    }
}

5.重复的子字符串

题目

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

示例 1:

1
2
3

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

示例 2:

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

示例 3:

1
2
3

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

提示：

1 <= s.length <= 104
s 由小写英文字母组成

思路

如果一个字符串能由它的子串重复多次构成，那它的子串一定是可以从开头开始截取的，所以只需要从开头开始截取不同的子串，再进行判断。

所以一个 for 循环获取子串的终止位置就行了。而且遍历的时候都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。下面就是暴力破解的代码：

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力解法
        for (int i = 0; i < s.length() / 2; i++) {
            String sub = s.substring(0, i + 1);
            if (s.length() % sub.length() != 0) {
                continue;
            }
            int index = 0;
            int loop = s.length() / sub.length();
            int start;
            while (index < loop) {
                start = index * sub.length();
                if (s.substring(start, start + sub.length()).equals(sub)) {
                    index++;
                    continue;
                } else {
                    break;
                }
            }
            if (index == loop) {
                return true;
            }
        }
        return false;
    }
}

这题还能用 KMP 算法求解。

主要是利用 next 数组求解。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = getNext(s);
        int len = s.length();
        // (len - next[len - 1] - 1)表示周期的长度
        // 数组长度减去最长相同前后缀的长度相当于是一个周期的长度，如果这个周期长度可以被数组长度整除，
        // 就说明整个数组就是这个周期的循环。
        if (next[len - 1] >= 0 && len % (len - next[len - 1] - 1) == 0) {
            return true;
        }
        return false;
    }

    // 获取next数组
    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        next[0] = -1;
        for (int i = 1; i < s.length(); i++) {
            int temp = next[i - 1];
            while (temp >= 0 && s.charAt(temp + 1) != s.charAt(i)) {
                temp = next[temp];
            }
            if (s.charAt(temp + 1) == s.charAt(i)) {
                next[i] = temp + 1;
            } else {
                next[i] = -1;
            }
        }
        return next;
    }
}

总结篇

字符串类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。
- 双指针法是字符串处理的常客。
- KMP 算法是字符串查找最重要的算法，要知道怎么获取 next 数组，并且如何使用它。