本文首發于我的個人部落格： 尾尾部落
1. KMP 算法
談到字元串問題，不得不提的就是 KMP 算法，它是用來解決字元串查找的問題，可以在一個字元串（S）中查找一個子串（W）出現的位置。KMP 算法把字元比對的時間複雜度縮小到 O(m+n) ,而空間複雜度也隻有O(m)。因為“暴力搜尋”的方法會反複回溯主串，導緻效率低下，而KMP算法可以利用已經部分比對這個有效資訊，保持主串上的指針不回溯，通過修改子串的指針，讓模式串盡量地移動到有效的位置。
具體算法細節請參考：
1.1 BM 算法
BM算法也是一種精确字元串比對算法，它采用從右向左比較的方法，同時應用到了兩種啟發式規則，即壞字元規則 和好字尾規則 ，來決定向右跳躍的距離。基本思路就是從右往左進行字元比對，遇到不比對的字元後從壞字元表和好字尾表找一個最大的右移值，将模式串右移繼續比對。
2. 替換空格
劍指offer： 替換空格 請實作一個函數，将一個字元串中的每個空格替換成“%20”。例如，當字元串為We Are Happy.則經過替換之後的字元串為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: 最長公共字首 編寫一個函數來查找字元串數組中的最長公共字首。如果不存在公共字首，傳回空字元串 ""。
image
首先對字元串數組進行排序，然後拿數組中的第一個和最後一個字元串進行比較，從第 0 位開始，如果相同，把它加入 res 中，不同則退出。最後傳回 res
class 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: 最長回文串 給定一個包含大寫字母和小寫字母的字元串，找到通過這些字母構造成的最長的回文串。在構造過程中，請注意區分大小寫。比如 "Aa" 不能當做一個回文字元串。
統計字母出現的次數即可，雙數才能構成回文。因為允許中間一個數單獨出現，比如“abcba”，是以如果最後有字母落單，總長度可以加 1。
class Solution {
public int longestPalindrome(String s) {
HashSet<Character> hs = new HashSet<>();
int len = s.length();
int count = 0;
if(len == 0)
return 0;
for(int i = 0; i<len; i++){
if(hs.contains(s.charAt(i))){
hs.remove(s.charAt(i));
count++;
}else{
hs.add(s.charAt(i));
}
}
return hs.isEmpty() ? count * 2 : count * 2 + 1;
}
}
4.1 驗證回文串
驗證回文串給定一個字元串，驗證它是否是回文串，隻考慮字母和數字字元，可以忽略字母的大小寫。
說明：本題中，我們将空字元串定義為有效的回文串。
兩個指針比較頭尾。要注意隻考慮字母和數字字元，可以忽略字母的大小寫。
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 最長回文子串
最長回文子串 給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為1000。
以某個元素為中心，分别計算偶數長度的回文最大長度和奇數長度的回文最大長度。
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 最長回文子序列
最長回文子序列給定一個字元串s，找到其中最長的回文子序列。可以假設s的最大長度為1000。
最長回文子序列和上一題最長回文子串的差別是，子串是字元串中連續的一個序列，而子序列是字元串中保持相對位置的字元序列，例如，"bbbb"可以使字元串"bbbab"的子序列但不是子串。
動态規劃：
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. 字元串的排列
字元串的排列給定兩個字元串 s1 和 s2，寫一個函數來判斷 s2 是否包含 s1 的排列。
換句話說，第一個字元串的排列之一是第二個字元串的子串。
我們不用真的去算出s1的全排列，隻要統計字元出現的次數即可。可以使用一個哈希表配上雙指針來做。
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<l1; i++){
count[s1.charAt(i) - 'a']++;
count[s2.charAt(i) - 'a']--;
}
if(allZero(count))
return true;
for(int i = l1; i<l2; i++){
count[s2.charAt(i) - 'a']--;
count[s2.charAt(i-l1) - 'a']++;
if(allZero(count))
return true;
}
return false;
}
public boolean allZero(int [] count){
int l = count.length;
for(int i = 0; i < l; i++){
if(count[i] != 0)
return false;
}
return true;
}
}
6. 列印字元串的全排列
輸入一個字元串,按字典序列印出該字元串中字元的所有排列。例如輸入字元串abc,則列印出由字元a,b,c所能排列出來的所有字元串abc,acb,bac,bca,cab和cba。
把問題拆解成簡單的步驟：
第一步求所有可能出現在第一個位置的字元（即把第一個字元和後面的所有字元交換[相同字元不交換]）；
第二步固定第一個字元，求後面所有字元的排列。這時候又可以把後面的所有字元拆成兩部分（第一個字元以及剩下的所有字元），依此類推。這樣，我們就可以用遞歸的方法來解決。
public class Solution {
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> 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. 第一個隻出現一次的字元
劍指offer: 第一個隻出現一次的字元 在一個字元串(0<=字元串長度<=10000，全部由字母組成)中找到第一個隻出現一次的字元,并傳回它的位置, 如果沒有則傳回 -1.
先在hash表中統計各字母出現次數，第二次掃描直接通路hash表獲得次數。也可以用數組代替hash表。
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
int len = str.length();
if(len == 0)
return -1;
HashMap<Character, Integer> 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. 翻轉單詞順序列
翻轉單詞順序列 翻轉字元串裡的單詞
借助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. 旋轉字元串
旋轉字元串給定兩個字元串, A 和 B。
A 的旋轉操作就是将 A 最左邊的字元移動到最右邊。 例如, 若 A = 'abcde'，在移動一次之後結果就是'bcdea' 。如果在若幹次旋轉操作之後，A 能變成B，那麼傳回True。
一行代碼搞定
class Solution {
public boolean rotateString(String A, String B) {
return A.length() == B.length() && (A+A).contains(B);
}
}
9.1 左旋轉字元串
左旋轉字元串 彙編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字元串模拟這個指令的運算結果。對于一個給定的字元序列S，請你把其循環左移K位後的序列輸出。例如，字元序列S=”abcXYZdef”,要求輸出循環左移3位後的結果，即“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 反轉字元串
反轉字元串 編寫一個函數，其作用是将輸入的字元串反轉過來。
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. 把字元串轉換成整數
把字元串轉換成整數 将一個字元串轉換成一個整數(實作Integer.valueOf(string)的功能，但是string不符合數字要求時傳回0)，要求不能使用字元串轉換整數的庫函數。 數值為0或者字元串不是一個合法的數值則傳回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. 正規表達式比對
正規表達式比對 請實作一個函數用來比對包括’.’和’*’的正規表達式。模式中的字元’.’表示任意一個字元，而’*’表示它前面的字元可以出現任意次（包含0次）。 在本題中，比對是指字元串的所有字元比對整個模式。例如，字元串”aaa”與模式”a.a”和”ab*ac*a”比對，但是與”aa.a”和”ab*a”均不比對
這裡我們采用dp[i+1][j+1]代表s[0..i]比對p[0..j]的結果，結果自然是采用布爾值True/False來表示。
首先，對邊界進行指派，顯然dp[0][0] = true，兩個空字元串的比對結果自然為True;
接着，我們對dp[0][j+1]進行指派，因為 i=0 是空串，如果一個空串和一個比對串想要比對成功，那麼隻有可能是p.charAt(j) == '*' && dp[0][j-1]
之後，就可以愉快地使用動态規劃遞推方程了。
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 dp[s.length()][p.length()];
}
12. 表示數值的字元串
表示數值的字元串 請實作一個函數用來判斷字元串是否表示數值（包括整數和小數）。例如，字元串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示數值。 但是”12e”,”1a3.14″,”1.2.3″,”+-5″和”12e+4.3″都不是。
設定三個标志符分别記錄“+/-”、“e/E”和“.”是否出現過。
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. 字元流中第一個不重複的字元
字元流中第一個不重複的字元 請實作一個函數用來找出字元流中第一個隻出現一次的字元。例如，當從字元流中隻讀出前兩個字元”go”時，第一個隻出現一次的字元是”g”。當從該字元流中讀出前六個字元“google”時，第一個隻出現一次的字元是”l”。
用一個哈希表來存儲每個字元及其出現的次數，另外用一個字元串 s 來儲存字元流中字元的順序。
import java.util.HashMap;
public class Solution {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
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 '#';
}
}