1. KMP 算法
談到字符串問題，不得不提的就是 KMP 算法，它是用來解決字符串查找的問題，可以在一個字符串（S）中查找一個子串（W）出現(xiàn)的位置。KMP 算法把字符匹配的時間復(fù)雜度縮小到 O(m+n) ,而空間復(fù)雜度也只有O(m)。因為“暴力搜索”的方法會反復(fù)回溯主串，導(dǎo)致效率低下，而KMP算法可以利用已經(jīng)部分匹配這個有效信息，保持主串上的指針不回溯，通過修改子串的指針，讓模式串盡量地移動到有效的位置。
具體算法細(xì)節(jié)請參考：
- 字符串匹配的KMP算法
- 從頭到尾徹底理解KMP
- 如何更好的理解和掌握 KMP 算法?
- KMP 算法詳細(xì)解析
- 圖解 KMP 算法
- 汪都能聽懂的KMP字符串匹配算法【雙語字幕】
- KMP字符串匹配算法1
1.1 BM 算法BM算法也是一種精確字符串匹配算法，它采用從右向左比較的方法，同時應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。基本思路就是從右往左進(jìn)行字符匹配，遇到不匹配的字符后從壞字符表和好后綴表找一個最大的右移值，將模式串右移繼續(xù)匹配。 字符串匹配的KMP算法
2. 替換空格
劍指offer：替換空格 請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
public class Solution { public String replaceSpace(StringBuffer str) { StringBuffer res = new StringBuffer(); int len = str.length() - 1; for(int i = len; i >= 0; i--){ if(str.charAt(i) == ' ') res.append('02%'); else res.append(str.charAt(i)); } return res.reverse().toString(); }}
3. 最長公共前綴
Leetcode: 最長公共前綴 編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ''。
首先對字符串?dāng)?shù)組進(jìn)行排序，然后拿數(shù)組中的第一個和最后一個字符串進(jìn)行比較，從第 0 位開始，如果相同，把它加入 res 中，不同則退出。最后返回 resclass Solution { public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ''; Arrays.sort(strs); char [] first = strs[0].toCharArray(); char [] last = strs[strs.length - 1].toCharArray(); StringBuffer res = new StringBuffer(); int len = first.length < last.length="" first.length="" :="" last.length;="" int="" i="0;" while(i="">< len){="" if(first[i]="=" last[i]){="" res.append(first[i]);="" i++;="" }="" else="" break;="" }="" return="" res.tostring();="">
4. 最長回文串
LeetCode: 最長回文串 給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構(gòu)造成的最長的回文串。在構(gòu)造過程中，請注意區(qū)分大小寫。比如 'Aa' 不能當(dāng)做一個回文字符串。
統(tǒng)計字母出現(xiàn)的次數(shù)即可，雙數(shù)才能構(gòu)成回文。因為允許中間一個數(shù)單獨出現(xiàn)，比如“abcba”，所以如果最后有字母落單，總長度可以加 1。class Solution { public int longestPalindrome(String s) { HashSet hs = new HashSet<>(); int len = s.length(); int count = 0; if(len == 0) return 0; for(int i = 0; i
4.1 驗證回文串Leetcode: 驗證回文串 給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。 說明：本題中，我們將空字符串定義為有效的回文串。
兩個指針比較頭尾。要注意只考慮字母和數(shù)字字符，可以忽略字母的大小寫。
class Solution { public boolean isPalindrome(String s) { if(s.length() == 0) return true; int l = 0, r = s.length() - 1; while(l < r){="" if(!character.isletterordigit(s.charat(l))){="" l++;="" }else="" if(!character.isletterordigit(s.charat(r))){="" r--;="" }else{="" if(character.tolowercase(s.charat(l))="" !="Character.toLowerCase(s.charAt(r)))" return="" false;="" l++;="" r--;="" }="" }="" return="" true;="">
4.2 最長回文子串LeetCode: 最長回文子串 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為1000。
以某個元素為中心，分別計算偶數(shù)長度的回文最大長度和奇數(shù)長度的回文最大長度。class Solution { private int index, len; public String longestPalindrome(String s) { if(s.length() < 2)="" return="" s;="" for(int="" i="0;" i="">< s.length()-1;="" i++){="" palindromehelper(s,="" i,="" i);="" palindromehelper(s,="" i,="" i+1);="" }="" return="" s.substring(index,="" index+len);="" }="" public="" void="" palindromehelper(string="" s,="" int="" l,="" int="" r){="" while(l="">= 0 && r < s.length()="" &&="" s.charat(l)="=" s.charat(r)){="" l--;="" r++;="" }="" if(len="">< r="" -="" l="" -="" 1){="" index="l" +="" 1;="" len="r" -="" l="" -="" 1;="" }="">
4.3 最長回文子序列LeetCode: 最長回文子序列 給定一個字符串s，找到其中最長的回文子序列?？梢约僭O(shè)s的最大長度為1000。 最長回文子序列和上一題最長回文子串的區(qū)別是，子串是字符串中連續(xù)的一個序列，而子序列是字符串中保持相對位置的字符序列，例如，'bbbb'可以使字符串'bbbab'的子序列但不是子串。
動態(tài)規(guī)劃： dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])class Solution { public int longestPalindromeSubseq(String s) { int len = s.length(); int [][] dp = new int[len][len]; for(int i = len - 1; i>=0; i--){ dp[i][i] = 1; for(int j = i+1; j < len;="" j++){="" if(s.charat(i)="=" s.charat(j))="" dp[i][j]="dp[i+1][j-1]" +="" 2;="" else="" dp[i][j]="Math.max(dp[i+1][j]," dp[i][j-1]);="" }="" }="" return="" dp[0][len-1];="">
5. 字符串的排列
Leetcode: 字符串的排列 給定兩個字符串 s1 和 s2，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。 換句話說，第一個字符串的排列之一是第二個字符串的子串。
我們不用真的去算出s1的全排列，只要統(tǒng)計字符出現(xiàn)的次數(shù)即可。可以使用一個哈希表配上雙指針來做。class Solution { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); int [] count = new int [128]; if(l1 > l2) return false; for(int i = 0; i< l;="" i++){="" if(count[i]="" !="0)" return="" false;="" }="" return="" true;="">
6. 打印字符串的全排列
劍指offer：字符串的排列 輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
把問題拆解成簡單的步驟： 第一步求所有可能出現(xiàn)在第一個位置的字符（即把第一個字符和后面的所有字符交換[相同字符不交換]）； 第二步固定第一個字符，求后面所有字符的排列。這時候又可以把后面的所有字符拆成兩部分（第一個字符以及剩下的所有字符），依此類推。這樣，我們就可以用遞歸的方法來解決。
public class Solution { ArrayList res = new ArrayList(); public ArrayList Permutation(String str) { if(str == null) return res; PermutationHelper(str.toCharArray(), 0); Collections.sort(res); return res; } public void PermutationHelper(char[] str, int i){ if(i == str.length - 1){ res.add(String.valueOf(str)); }else{ for(int j = i; j < str.length;="" j++){="" if(j!="i" &&="" str[i]="=" str[j])="" continue;="" swap(str,="" i,="" j);="" permutationhelper(str,="" i+1);="" swap(str,="" i,="" j);="" }="" }="" }="" public="" void="" swap(char[]="" str,="" int="" i,="" int="" j)="" {="" char="" temp="str[i];" str[i]="str[j];" str[j]="temp;">
7. 第一個只出現(xiàn)一次的字符
劍指offer: 第一個只出現(xiàn)一次的字符 在一個字符串(0<><=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回="">
先在hash表中統(tǒng)計各字母出現(xiàn)次數(shù)，第二次掃描直接訪問hash表獲得次數(shù)。也可以用數(shù)組代替hash表。
import java.util.HashMap;public class Solution { public int FirstNotRepeatingChar(String str) { int len = str.length(); if(len == 0) return -1; HashMap map = new HashMap<>(); for(int i = 0; i < len;="" i++){="" if(map.containskey(str.charat(i))){="" int="" value="map.get(str.charAt(i));" map.put(str.charat(i),="" value+1);="" }else{="" map.put(str.charat(i),="" 1);="" }="" }="" for(int="" i="0;" i="">< len;="" i++){="" if(map.get(str.charat(i))="=" 1)="" return="" i;="" }="" return="" -1;="">
8. 翻轉(zhuǎn)單詞順序列
劍指offer: 翻轉(zhuǎn)單詞順序列 LeetCode: 翻轉(zhuǎn)字符串里的單詞
借助trim()和 split()就很容易搞定
public class Solution { public String reverseWords(String s) { if(s.trim().length() == 0) return s.trim(); String [] temp = s.trim().split(' +'); String res = ''; for(int i = temp.length - 1; i > 0; i--){ res += temp[i] + ' '; } return res + temp[0]; }}
9. 旋轉(zhuǎn)字符串
Leetcode: 旋轉(zhuǎn)字符串 給定兩個字符串, A 和 B。 A 的旋轉(zhuǎn)操作就是將 A 最左邊的字符移動到最右邊。 例如, 若 A = 'abcde'，在移動一次之后結(jié)果就是'bcdea' 。如果在若干次旋轉(zhuǎn)操作之后，A 能變成B，那么返回True。
一行代碼搞定class Solution { public boolean rotateString(String A, String B) { return A.length() == B.length() && (A+A).contains(B); }}
9.1 左旋轉(zhuǎn)字符串劍指offer: 左旋轉(zhuǎn)字符串 匯編語言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個簡單的任務(wù)，就是用字符串模擬這個指令的運算結(jié)果。對于一個給定的字符序列S，請你把其循環(huán)左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”。是不是很簡單？OK，搞定它！
在第 n 個字符后面將切一刀，將字符串分為兩部分，再重新并接起來即可。注意字符串長度為 0 的情況。
public class Solution { public String LeftRotateString(String str,int n) { int len = str.length(); if(len == 0) return ''; n = n % len; String s1 = str.substring(n, len); String s2 = str.substring(0, n); return s1+s2; }}
9.2 反轉(zhuǎn)字符串LeetCode: 反轉(zhuǎn)字符串 編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。
class Solution { public String reverseString(String s) { if(s.length() < 2)="" return="" s;="" int="" l="0," r="s.length()" -="" 1;="" char="" []="" strs="s.toCharArray();" while(l="">< r){="" char="" temp="strs[l];" strs[l]="strs[r];" strs[r]="temp;" l++;="" r--;="" }="" return="" new="" string(strs);="">
10. 把字符串轉(zhuǎn)換成整數(shù)
劍指offer: 把字符串轉(zhuǎn)換成整數(shù) 將一個字符串轉(zhuǎn)換成一個整數(shù)(實現(xiàn)Integer.valueOf(string)的功能，但是string不符合數(shù)字要求時返回0)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)。 數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0。
public class Solution { public int StrToInt(String str) { if(str.length() == 0) return 0; int flag = 0; if(str.charAt(0) == '+') flag = 1; else if(str.charAt(0) == '-') flag = 2; int start = flag > 0 ? 1 : 0; long res = 0; while(start < str.length()){="" if(str.charat(start)=""> '9' || str.charAt(start) < '0')="" return="" 0;="" res="res" *="" 10="" +="" (str.charat(start)="" -="" '0');="" start="" ++;="" }="" return="" flag="=" 2="" -(int)res="" :="" (int)res;="">
11. 正則表達(dá)式匹配
劍指offer：正則表達(dá)式匹配 請實現(xiàn)一個函數(shù)用來匹配包括’.’和’*’的正則表達(dá)式。模式中的字符’.’表示任意一個字符，而’*’表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串”aaa”與模式”a.a”和”ab*ac*a”匹配，但是與”aa.a”和”ab*a”均不匹配
動態(tài)規(guī)劃： 這里我們采用dp[i+1][j+1]代表s[0..i]匹配p[0..j]的結(jié)果，結(jié)果自然是采用布爾值True/False來表示。 首先，對邊界進(jìn)行賦值，顯然dp[0][0] = true，兩個空字符串的匹配結(jié)果自然為True; 接著，我們對dp[0][j+1]進(jìn)行賦值，因為 i=0 是空串，如果一個空串和一個匹配串想要匹配成功，那么只有可能是p.charAt(j) == '*' && dp[0][j-1] 之后，就可以愉快地使用動態(tài)規(guī)劃遞推方程了。public boolean isMatch(String s, String p) { if (s == null || p == null) { return false; } boolean[][] dp = new boolean[s.length()+1][p.length()+1]; dp[0][0] = true; for (int j = 0; i < p.length();="" j++)="" {="" if="" (p.charat(j)="=" '*'="" &&="" dp[0][j-1])="" {="" dp[0][j+1]="true;" }="" }="" for="" (int="" i="0" ;="" i="">< s.length();="" i++)="" {="" for="" (int="" j="0;" j="">< p.length();="" j++)="" {="" if="" (p.charat(j)="=" '.')="" {="" dp[i+1][j+1]="dp[i][j];" }="" if="" (p.charat(j)="=" s.charat(i))="" {="" dp[i+1][j+1]="dp[i][j];" }="" if="" (p.charat(j)="=" '*')="" {="" if="" (p.charat(j-1)="" !="s.charAt(i)" &&="" p.charat(j-1)="" !='.' )="" {="" dp[i+1][j+1]="dp[i+1][j-1];" }="" else="" {="" dp[i+1][j+1]="(dp[i+1][j]" ||="" dp[i][j+1]="" ||="" dp[i+1][j-1]);="" }="" }="" }="" }="" return="">
12. 表示數(shù)值的字符串
劍指offer: 表示數(shù)值的字符串 請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示數(shù)值。 但是”12e”,”1a3.14″,”1.2.3″,”+-5″和”12e+4.3″都不是。
設(shè)置三個標(biāo)志符分別記錄“+/-”、“e/E”和“.”是否出現(xiàn)過。
public class Solution { public boolean isNumeric(char[] str) { int len = str.length; boolean sign = false, decimal = false, hasE = false; for(int i = 0; i < len;="" i++){="" if(str[i]="=" '+'="" ||="" str[i]="=" '-'){="" if(!sign="" &&="" i=""> 0 && str[i-1] != 'e' && str[i-1] != 'E') return false; if(sign && str[i-1] != 'e' && str[i-1] != 'E') return false; sign = true; }else if(str[i] == 'e' || str[i] == 'E'){ if(i == len - 1) return false; if(hasE) return false; hasE = true; }else if(str[i] == '.'){ if(hasE || decimal) return false; decimal = true; }else if(str[i] < '0'="" ||="" str[i]=""> '9') return false; } return true; }}
13. 字符流中第一個不重復(fù)的字符
劍指offer: 字符流中第一個不重復(fù)的字符 請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個字符”go”時，第一個只出現(xiàn)一次的字符是”g”。當(dāng)從該字符流中讀出前六個字符“google”時，第一個只出現(xiàn)一次的字符是”l”。
用一個哈希表來存儲每個字符及其出現(xiàn)的次數(shù)，另外用一個字符串 s 來保存字符流中字符的順序。
import java.util.HashMap;public class Solution { HashMap map = new HashMap(); StringBuffer s = new StringBuffer(); //Insert one char from stringstream public void Insert(char ch) { s.append(ch); if(map.containsKey(ch)){ map.put(ch, map.get(ch)+1); }else{ map.put(ch, 1); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(int i = 0; i < s.length();="" i++){="" if(map.get(s.charat(i))="=" 1)="" return="" s.charat(i);="" }="" return="" '#';="">
