LeetCode_字符串

一、字符串

1、反转字符串（力扣344）

// 双指针public void reverseString(char[] s) {int leftIndex = 0, rightIndex = s.length - 1;while (leftIndex < rightIndex) {char temp = s[leftIndex];s[leftIndex] = s[rightIndex];s[rightIndex] = temp;leftIndex ++;rightIndex --;}}

2、反转字符串 II（力扣541）

	public  String reverseStr(String s, int k) {int len = s.length();char[] c = s.toCharArray();for(int i = 0;i < len;i += 2 * k){reverse(c,i,Math.min(i + k,len) - 1);}return new String(c);}//反转传入的字符数组public void reverse(char[] c,int left,int right){while(left < right){char temp = c[left];c[left] = c[right];c[right] = temp;left ++;right --;}}

3、替换数字（卡玛网）

import java.util.*;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.next();char[] charArray = str.toCharArray();int len = charArray.length;/* 计算结果数组的长度 */for (int i = 0; i < charArray.length; i++) {if (charArray[i] >= '0' && charArray[i] <= '9'){len += 5;}}char[] resArray = new char[len];/* 从后向前依次处理 */for (int i = resArray.length - 1, j = charArray.length - 1; j >= 0; j--) {if (charArray[j] >= '0' && charArray[j] <= '9'){resArray[i --] = 'r';resArray[i --] = 'e';resArray[i --] = 'b';resArray[i --] = 'm';resArray[i --] = 'u';resArray[i --] = 'n';} else {resArray[i --] = charArray[j];}}System.out.println(resArray);}}

4、翻转字符串里的单词（力扣151）

	public static String reverseWords(String s) {// 去掉首位空格及单词之前多余的空格StringBuilder sb = trimSpaces(s);// 先翻转整个字符串reverse(sb,0,sb.length() - 1);// 再单独翻转单个单词reverseEachWords(sb);return sb.toString();      }public static StringBuilder trimSpaces(String s){int left = 0,right = s.length() - 1;// 去掉字符串开头的空白字符while(left <= right && s.charAt(left) == ' '){left ++;}// 去掉字符串末尾的空白字符while(left <= right && s.charAt(right) == ' '){right --;}// 将字符串间多余的空白字符去除StringBuilder sb = new StringBuilder();while(left <= right){char c = s.charAt(left);if(c != ' '){sb.append(c);}else if(sb.charAt(sb.length() - 1) != ' '){sb.append(c);}left ++;}return sb;}// 先翻转整个字符串public static void reverse(StringBuilder sb, int left, int right) {while (left < right) {char tmp = sb.charAt(left);sb.setCharAt(left++, sb.charAt(right));sb.setCharAt(right--, tmp);}}// 再单独翻转单个单词public static void reverseEachWords(StringBuilder sb){int len = sb.length();int start = 0,end = 0;while(start < len){while(end < len && sb.charAt(end) != ' '){end ++;}reverse(sb,start,end - 1);start = end + 1;end ++;}}

	public String reverseWords(String s) {int len = s.length();int left = 0,right = len - 1;// 去掉字符串开头的空白字符while(left <= right && s.charAt(left) == ' '){left ++;}// 去掉字符串末尾的空白字符while(left <= right && s.charAt(right) == ' '){right --;}Deque<String> deque = new ArrayDeque<String>();StringBuilder sb = new StringBuilder();//从前往后遍历，将单词添加到队列的前端while(left <= right){char c = s.charAt(left);if(sb.length() != 0 && c == ' '){deque.offerFirst(sb.toString());//清空StringBuildersb.setLength(0);}else if(c != ' '){sb.append(c);}left ++;}//不要忘了这一步，当遍历完最后一个单词，直接退出while循环，此时队列中还没有加入最后一个单词deque.offerFirst(sb.toString());return String.join(" ",deque);}

5、实现 strStr()（力扣28）

5.1、实现 strStr()（力扣28）

    //1.利用substringpublic int strStr(String haystack, String needle) {if(needle == "") return 0;int len1 = haystack.length(),len2 = needle.length();for(int i = 0;i < len1 - len2 + 1;i ++){if(haystack.substring(i,i + len2).equals(needle)){return i;}}return -1;}

//2.暴力匹配public int strStr2(String haystack, String needle) {char[] c1 = haystack.toCharArray();char[] c2 = needle.toCharArray();int s1Length = haystack.length();int s2Length = needle.length();int i = 0,j = 0;while (i < s1Length && j < s2Length){if (c1[i] == c2[j]){i ++;j ++;if (j == s2Length){//返回第一次出现的位置return i - j;}}else{//回到上一次开始比较的下一个位置i = i - j  + 1;j = 0;}}return -1;}//3.暴力匹配public int strStr3(String haystack, String needle) {char[] c1 = haystack.toCharArray();char[] c2 = needle.toCharArray();int m = c1.length;int n = c2.length;for(int i = 0;i <= m - n;i ++){int index1 = i,index2 = 0;while(index2 < n && c1[index1] == c2[index2]){index1 ++;index2 ++;}if(index2 == n) return index1 - index2;}return -1;}

5.2、KMP算法

当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。看这里
n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是$O(n)$，之前还要单独生成next数组，时间复杂度是$O(m)$。所以整个KMP算法的时间复杂度是$O(n+m)$的。

//4.KMP算法public int strStr4(String s1,String s2){if(s2 == " ") return 0;int[] next = kmpNext(s2);for (int i = 0,j = 0; i < s1.length(); i++) {/** s1:文本串   s2:模式串* a a b a a b a a f*           i* 0 1 2 3 4 5* a a b a a f*           j**此时b != f , j 回退到 j == 2,因为知道文本串中有aa和模式串中aa相等，*而模式串自己0和1位置的aa和3,4位置的aa相等，所以aa不用再做比较。*如果j==2时仍然不相等，接着回退，以此类推...*所以用while* */while (j > 0 && s1.charAt(i) != s2.charAt(j)){j = next[j - 1];}if (s1.charAt(i) == s2.charAt(j)) {j ++;}if (j == s2.length()){return i - j + 1;}}return -1;}//获取一个字符串的部分匹配值表public static int[] kmpNext(String s){//1.初始化int[] next = new int[s.length()];next[0] = 0;for (int i = 1,j = 0; i < s.length(); i++) {/** a b a b a b a f*              * 0 0 1 2 3 4 5 0** 前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串* 后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串* */while (j > 0 && s.charAt(i) != s.charAt(j)){j = next[j - 1];}//3.前后缀相同if (s.charAt(i) == s.charAt(j)){j ++;}//4.填充next数组next[i] = j;}return next;}

6、重复的子字符串（力扣459）

    // 1.将s中所有可能的子串全部挑出来，看子串是否能组成spublic boolean repeatedSubstringPattern(String s) {int len = s.length();for(int i = 1;i <= len / 2;i ++){//做一个优化if(len % i != 0) continue;StringBuilder sb = new StringBuilder();while(sb.length() < len){sb.append(s.substring(0,i));}if(sb.toString().equals(s)){return true;}}return false;}

	//2.枚举public boolean repeatedSubstringPattern(String s) {int len = s.length();//i是可能的子串的长度for(int i = 1;i <= len / 2;i ++){if(len % i == 0){boolean match = true;for(int j = i;j < len;j ++){if(s.charAt(j) != s.charAt(j - i)){match = false;break;}}if(match){return true;}}}return false;}

	//3.使用库函数public boolean repeatedSubstringPattern3(String s) {//indexOf(s,index) 从index下标开始找s首次出现的起始下标//如果s = ab ,s + s = abab,起始下标==s.length()，返回false//如果s=abab,s + s = abababab,起始下标为2<4,返回true//其实就是令s1=s,s2=s,令t=s1+s2,看是否能从t中找到s的第一次出现位置//且此位置不为0或s.length(),即看是否能利用s1的后面组合s2的前面得到sreturn (s + s).indexOf(s,1) < s.length();}

//4.kmp算法，思路和3一样，只不过查找过程换为kmp算法public boolean repeatedSubstringPattern4(String s) {String t = s + s;return Kmp(t,s) == s.length() ? false : true;}public int Kmp(String t,String s){int[] next = getNext(s);for(int i = 1,j = 0;i < t.length();i ++){while(j > 0 && t.charAt(i) != s.charAt(j)){j = next[j - 1];}if(t.charAt(i) == s.charAt(j)){j ++;}if(j == s.length()){return i - j + 1;}}return -1;}public int[] getNext(String s){int[] next = new int[s.length()];next[0] = 0;for(int i = 1,j = 0;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;}return next;}

//5.kmp算法//5.kmp算法public boolean repeatedSubstringPattern5(String s) {int len = s.length();int[] next = new int[len];next[0] = 0;for(int i = 1,j = 0;i < len;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;}//构造出next数组之后，以abab为例，最长公共前后缀的长度是2,4 % (4 - 2) == 0,返回true//假设s串是可以由数个子串构成的，那么len - 最长公共前后缀的长度后，就是可构成s的最短子串//的长度，最后看len是否是这个最短子串长度的整数倍if(next[len - 1] > 0 && len % (len - next[len - 1]) == 0){return true;}return false;}