字符串系列
一、字符串基础
1.理论基础
（1）定义字符串
-
直接赋值：
//此时数据abc声明在方法区中的字符串常量池中 String s = "abc";
-
通过new+构造器的方式：
//此时s保存的地址值，是数据在堆空间中开辟以后对应的地址值 String s = new String("abc");
（2）StringBuilder和StringBuffer
二者都不同于String，当修改String字符串时，是在内存中创建一个新的字符串，并把地址传给 String 对象，因此比较浪费空间；而 StringBuffer 和 StringBuilder 是在初始时创建一个容器，当修改的时候会修改容器中的内容，而不是创建一个新的容器。所以如果需要频繁改变字符串的话，最好不要使用String，而是利用StringBuffer 和 StringBuilder来修改String字符串。
-
StringBuffer和StringBuilder的区别：
StringBuilder：非线程安全的，并发处理的，性能稍快
StringBuffer：线程安全的，同步处理的，性能稍慢 -
常用方法基本相同：
StringBuilder(或StringBuffer) append( x )
将 x 追加到容器中，空容器也能用！
StringBuilder delete(int start, int end)
删除从 start 开始到为 end - 1 的子串，即左闭右开。
StringBuilder insert(int idx, x )
在idx处插入 x 的内容。 StringBuilder replace(int start, int end, String str)
将从 start 开始到 end - 1的子串替换为 str 。如果 str 的长度比子串长，容器将被延长以容纳str。
2.★常用API
|
char[] toCharArray() |
★将此字符串转换为新的字符数组。 |
|
返回参数的字符串表示形式。
用法：String.valueOf(xxx)
|
|
int length() |
返回字符串长度。 |
 |
返回指定字符或字符子串在原字符串中第一次出现的索引。 也可以指定从哪个索引开始搜索。 |
|
|
|
String trim() |
trim是修剪的意思。
删除字符串开头和末尾的所有空格。
|
|
String[] split(String regex) |
按给定的字符串regex切割字符串，返回以切割后每一部分为元素的字符串数组。 |
|
static String join(String delimiter,String... strs) |
将多个字符串str通过delimiter拼接成一个新的字符串。 String message = String.join("-", "Java", "is", "cool"); //返回值："Java-is-cool" |
二、★KMP算法
1.什么是KMP算法？
KMP的主要思想是：出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。主要利用前缀表来实现。
KMP主要应用在字符串匹配(28. 找出字符串中第一个匹配项的下标)上，还可以用来求解重复子串问题(459. 重复的子字符串)。
2.前缀与后缀
对于一个字符串，前缀是包含首字符、不包含尾字符的子串；后缀是包含尾字符，不包含首字符的子串。
如"abcde"的前缀{a,ab,abc,abcd}，后缀{bcde,cde,de,e}。
如"abcde"的前缀{a,ab,abc,abcd}，后缀{bcde,cde,de,e}。
【tips】每个前缀一定包含首字符，每个后缀一定包含尾字符。
3.前缀表
前缀表是用来回退的，记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。用一个int数组来实现，一般称为next数组。
next数组的长度等于模式串的长度，next[i]的值代表了 如果模式串中 i 指向的字符与主串发生了不匹配，模式串该回退到哪个下标，开始重新匹配。
从上图中可以看出，主串中第六个字符 b 和 模式串的第六个字符 f不匹配了：如果暴力匹配，发现不匹配时就要从头重新匹配了； 但如果使用kmp算法的前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，即回退到模式串中第三个字符b(下标为2)继续开始匹配。
4.最长相等前后缀
（1）什么是最长相等前后缀？
最长相等前后缀就是一个子串所有相等的前缀和后缀中最长的那对前、后缀。举个例子：" aabaa "，先找到所有前缀{a,aa,aab,aaba}和所有后缀{abaa,baa,aa,a}，可以看到相等的前后缀有{a,aa}，那么最长相等前后缀就是aa。
（2）作用
KMP算法就是基于最长相等前后缀来实现的，如上面动图中在 f 和 b 时不匹配了，此时模式串该回退到哪呢？
——要看 f 之前那个子串(aabaa)的最长相等前后缀的长度。我们在(1)中求出来"aabaa"最长相等前后缀的长度为2，那么此时模式串应该回退到下标为 2 的位置即第三个字符 b 重新与主串进行匹配。
5.如何求前缀表？
/**
核心思想其实还是字符串的匹配问题，只不过是"我匹配我自己"，将后缀作为主串，前缀作为模式串。
求前缀表next的步骤:
1.初始化变量和next数组
2.处理前后缀不相等的情况
3.处理前后缀相等的情况
4.更新next数组
*/
void getNext(int[] next,String needle){
//1.初始化变量和next数组
//j指向前缀末尾，j还代表i之前(包括i)子串的最长相等前后缀的长度
int j=0;
//模式串首个字符的next值一定为0
next[0]=0;
//i指向后缀末尾
for(int i=1;i<next.length;i++){
//前后缀不相等，回退：直到退到头或前后缀相等为止
while(j>0&&needle.charAt(i)!=needle.charAt(j)){
//回退时不是退到上一个位置
j=next[j-1];
}
//前后缀相等
if(needle.charAt(i)==needle.charAt(j)){
//前后缀相等说明最长相等前后缀多了刚刚判断的前后缀相等的这个字符，所以长度要+1，即j+1
j++;
}
//更新前缀表
next[i]=j;
}
}
6.KMP算法的时间复杂度
n为文本串长度，m为模式串长度。因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程的时间复杂度是O(n)；然后之前还要单独求next数组，时间复杂度是O(m)，所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。
三、相关题目推荐
1. 344.反转字符串
-
思路：简单的双指针问题，反转链表 用的也是双指针，但是反转字符串比反转链表简单些。
public void reverseString(char[] s) { //双指针 int left=0; int right=s.length-1; while(left<right){ char temp; temp=s[left]; s[left]=s[right]; s[right]=temp; left++; right--; } }
2. 541. 反转字符串II
-
思路：这道题有点被题目描述带跑了，其实就是从字符串起始位置开始，反转当前位置后的k个字符，然后移动到当前位置后的2k位置；同时如果当前位置后的字符数不够k个，就把不够k的这几个全反转。
public String reverseStr(String s, int k) { //String -> char[] char[] sArr=s.toCharArray(); //★★这里每次移动的步长我们不用 1 而用 2*k ！ for(int i=0;i<sArr.length; i+=2*k ){ //如果当前位置后的字符数少于 k 个，则将这部分字符全部反转 if(sArr.length-i<k){ reverse(sArr,i,sArr.length-1); }else{//如果当前位置后的字符数大于或等于 k 个，则反转当前位置后的 k 个字符 reverse(sArr,i,i+k-1); } } //★char[] -> String return new String(sArr); } //自定义反转字符串方法：反转的字符包含下标为end的字符，即左闭右闭。 public void reverse(char[] s,int start,int end){ while(start<end){ char temp=s[start]; s[start]=s[end]; s[end]=temp; start++; end--; } }
3. ★剑指 Offer 05. 替换空格
-
思路一：双指针法+倒序遍历。因为原字符串中每有一个空格字符，就需要替换成三个字符的 '%20'，即每有一个空格就需要多两个字符的位置。因此我们可以先扩充字符串，然后将其转为字符数组，再遍历数组，遇到空格字符就替换成'%20'。
★这里有个细节：倒序遍历。为什么要倒序遍历呢？
——因为数组中的删除和新增操作，都需要移动元素。比如这道题，每次添加元素都要将添加元素之后的所有元素向后移动，需要两层for循环(即时间复杂度为O(n))：一层找添加位置，一层移动元素。其实很多数组填充类的问题，都可以预先给数组扩容成填充后的大小，再从后向前进行操作，这样避免了从前向后填充元素时，每次添加都要将添加元素之后的所有元素向后移动的问题，时间复杂度就降为了O(n)。
public String replaceSpace(String s) { if(s==null || s.length()==0){ return s; } //扩充字符串，创建要补充的字符串空间，s每有一个空格，就需要多两个字符的位置 StringBuilder str = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if(s.charAt(i) == ' '){ //在str中创建两个字符的位置 str.append(" "); } } //若str没有空格，说明s中没有空格，直接返回 if(str.length() == 0){ return s; } //双指针：left指向原字符串的最后一个字符;right指向扩展后字符串的最后一个字符 int left=s.length()-1; //拼接原字符串与扩展空间，现在的s是扩展后的字符串了 s += str.toString(); int right = s.length()-1; char[] strArr = s.toCharArray(); //从后向前遍历，指针相遇说明替换完毕 while(left<right){ //是空格，替换 if(strArr[left]==' '){ strArr[right--]='0'; strArr[right--]='2'; strArr[right]='%'; }else{ //不是空格 strArr[right]=strArr[left]; } left--; right--; } return new String(strArr); } -
思路二：StringBuilder。创建一个新的字符串，逐字符复制原字符串，并在复制的过程判断：是空格则替换，否则直接复制。
public String replaceSpace(String s) { if(s==null||s.length()==0){ return s; } StringBuilder str=new StringBuilder(); //逐个字符复制字符串 for(int i=0;i<s.length();i++){ if (s.charAt(i) == ' ') { str.append("%20"); } else { str.append(s.charAt(i)); } } //StringBuilder -> String return str.toString(); }
4. ★151.翻转字符串里的单词
-
思路一：使用java内置函数。
public String reverseWords(String s) { String[] words = s.trim().split(" +"); Collections.reverse(Arrays.asList(words)); return String.join(" ", words); } -
★思路二：不使用API的双指针法。将字符串转为字符数组，整体翻转+局部反转，然后分三步实现：
①反转整个字符数组；
②反转单个单词；
③删除多余空格。public String reverseWords(String s) { if(s==null){ return s; } char[] strArr=s.toCharArray(); int len=strArr.length; //1.反转整个字符串(数组) reverseStrArr(strArr,0,len-1); //2.反转单个单词 reverseWord(strArr); //3.删除多余空格 return deleteSpace(strArr); } //反转字符数组的指定部分[左闭右闭] public void reverseStrArr(char[] strArr,int start,int end){ int left=start; int right=end; while(left<right){ char temp=strArr[left]; strArr[left]=strArr[right]; strArr[right]=temp; left++; right--; } } //★反转单个单词 public void reverseWord(char[] strArr){ int left=0; int right=0; while(right<strArr.length){ //找单词的首字母。注意：循环结束right指向首字母的位置 while(right<strArr.length && strArr[right]==' '){ right++; } //让left指向单词的首字母 left=right; //找该单词的最后一个字母。注意：循环结束right指向最后一个字母的下一个位置 while(right<strArr.length && strArr[right]!=' '){ right++; } //反转单个单词 reverseStrArr(strArr,left,right-1); } } //★★删除多余空格 public String deleteSpace(char[] strArr){ int left=0; int right=0; while(right<strArr.length){ //如果整个字符串开头有空格的话，先将right移动到第一个单词的首字母 while(right<strArr.length && strArr[right]==' '){ right++; } //原地保存单词 while(right<strArr.length && strArr[right]!=' '){ strArr[left]=strArr[right]; left++; right++; } //★将right移动到下一个单词的首字母。 while(right<strArr.length && strArr[right]==' '){ right++; } //★如果不是最后一个单词，就给单词后加空格 if(right<strArr.length){ strArr[left]=' '; left++; } } //将字符数组的0到left部分转为String返回 return String.valueOf(strArr,0,left); }
5. 剑指Offer58-II.左旋转字符串
-
思路：不申请额外空间实现左旋转。可以通过局部反转+整体反转达到左旋转的目的。
/** 1.反转前k个字符 2.反转剩下的字符 3.反转整个字符串 */ public String reverseLeftWords(String s, int k) { if(s==null){ return s; } char[] strArr = s.toCharArray(); int len=s.length(); //反转前k个字符 reverse(strArr,0,k-1); //反转剩下的字符 reverse(strArr,k,len-1); //反转整个字符串 reverse(strArr,0,len-1); return new String(strArr); } public void reverse(char[] strArr,int start,int end){ while(start<end){ char temp=strArr[start]; strArr[start++]=strArr[end]; strArr[end--]=temp; } }
6. ★★28. 找出字符串中第一个匹配项的下标
-
思路：KMP算法。这是一道使用kmp算法解决字符串匹配问题的经典题。
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++){ //不匹配，回退到j前一位的next值的位置，直到回退到头或匹配为止 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 needle){ //初始化 //j指向前缀末尾，j还代表i之前(包括i)子串的最长相等前后缀的长度 int j=0; //模式串首个字符的next值一定为0 next[0]=0; //i指向后缀末尾 for(int i=1;i<next.length;i++){ //前后缀不相等，回退 while(j>0&&needle.charAt(i)!=needle.charAt(j)){ j=next[j-1]; } //前后缀相等 if(needle.charAt(i)==needle.charAt(j)){ j++; } //更新前缀表 next[i]=j; } }
7. 459. 重复的子字符串
-
思路一：移动匹配。一个由重复的子串组成的字符串s="abcabc"，那么s的结构一定是这样由前后相同的子串组成的：
既然前、后都有相同的子串，用 s + s 组成的字符串 ss 中，原来后面的子串做前串，前面的子串做后串，不考虑 ss 开头和末尾的字符的话，就一定还能组成一个s，如图：
所以判断字符串s是否由重复子串组成，只要将两个s拼在一起，掐头去尾里面还出现一个s的话，就说明s是由重复子串组成。public boolean repeatedSubstringPattern(String s) { //s+s String ss=s+s; //掐头去尾 //找掐头去尾后的ss中有没有s return ss.substring(1,ss.length()-1).contains(s); //一行解决： //return (s+s).substring(1,s.length()*2-1).contains(s); } -
思路二：KMP算法。在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里拿字符串s="abababab" 来举例，ab就是最小重复单位，如图所示。如果字符串长度可以被 (字符串长度-最长相等前后缀的长度) 整除 ，则说明该字符串有重复的子字符串。 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
具体实现：先求出字符串的前缀表，然后判断字符串长度能否被(字符串长度 - next表最后一个值)整除，要注意保证next最后一位不为0。public boolean repeatedSubstringPattern(String s) { int sLen=s.length(); //求s的next表 int j=0; int[] next=new int[sLen]; next[0]=0; for(int i=1;i<sLen;i++){ while(j>0&&s.charAt(j)!=s.charAt(i)){ j=next[j-1]; } if(s.charAt(j)==s.charAt(i)){ j++; } next[i]=j; } //判断是否是重复的子字符串 //如果next最后一位为0，说明该字符串的最长相等前后缀长度为0，即没有最长相等前后缀，更没有可重复的子串了，所以首先要让next[sLen-1]>0，再判断s的长度能否整除最小重复字串的长度(sLen-next[sLen-1]) if(next[sLen-1]>0&&sLen%(sLen-next[sLen-1])==0){ return true; } return false; }
字节跳动公司氛围 642人发布