基础算法—字符串篇

基础算法—字符串篇

344. 反转字符串

思路

双指针

541. 反转字符串 II

思路

反转字符串

剑指 Offer 05. 替换空格

思路

替换空格

151. 反转字符串中的单词

思路

翻转字符串里的单词

680. 验证回文串 II

剑指 Offer 58 - II. 左旋转字符串

思路

s.substring

KMP

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

前缀表

前缀表（prefix table）==next数组，记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

举例：

要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

KMP详解1

文本串中第六个字符b 和 模式串的第六个字符f，不匹配了，从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。

最长公共前后缀

前缀：对于字符串 abcxxxxefg，我们称 abc 属于 abcxxxxefg 的某个前缀。
后缀：对于字符串 abcxxxxefg，我们称 efg 属于 abcxxxxefg 的某个后缀。

计算前缀表

如图：

KMP精讲5

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

KMP精讲6 长度为前2个字符的子串aa，最长相同前后缀的长度为1。

KMP精讲7 长度为前3个字符的子串aab，最长相同前后缀的长度0。

以此类推： 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图： KMP精讲8

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

KMP精讲2

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

构造next数组

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void getNext(int[] next,String s){
        //初始化，j指向前缀起始位置，i指向后缀起始位置。
        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];
            }
            //前后缀相同的情况，每有一个相等的长度就会+1
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            //生成前缀表,这里的j代表最长相等前后缀的长度
            next[i]=j;
        }
    }

KMP精讲3

使用next数组来匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//j 指向模式串起始位置，i指向文本串起始位置。
   int j=0;
   for (int i = 0; i < haystack.length(); i++) {
       while (j>0&&needle.charAt(j)!=haystack.charAt(i)){
           j=next[j-1];
       }
       if (needle.charAt(j)==haystack.charAt(i)){
           //计算已经匹配的长度
           j++;
       }
       //如果j的长度等于模式串的长度就说明文本串中出现了模式串
       if (j==needle.length()){
           return i-needle.length()+1;
       }
   }
   return -1;

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

459. 重复的子字符串

思路

重复的子字符串

686. 重复叠加字符串匹配

2430. 对字母串可执行的最大删除数