<!-- MarkdownTOC --> - [說明](#說明) - [1. KMP 算法](#1-kmp-算法) - [2. 替換空格](#2-替換空格) - [3. 最長公共前綴](#3-最長公共前綴) - [4. 回文串](#4-回文串) - [4.1. 最長回文串](#41-最長回文串) - [4.2. 驗證回文串](#42-驗證回文串) - [4.3. 最長回文子串](#43-最長回文子串) - [4.4. 最長回文子序列](#44-最長回文子序列) - [5. 括號匹配深度](#5-括號匹配深度) - [6. 把字符串轉換成整數](#6-把字符串轉換成整數) <!-- /MarkdownTOC --> > 授權轉載！ > > - 本文作者：wwwxmu > - 原文地址:https://www.weiweiblog.cn/13string/ 考慮到篇幅問題，我會分兩次更新這個內容。本篇文章只是原文的一部分，我在原文的基礎上增加了部分內容以及修改了部分代碼和注釋。另外，我增加了愛奇藝 2018 秋招 Java：`求給定合法括號序列的深度` 這道題。所有代碼均編譯成功，并帶有注釋，歡迎各位享用！ ## 1. KMP 算法 談到字符串問題，不得不提的就是 KMP 算法，它是用來解決字符串查找的問題，可以在一個字符串（S）中查找一個子串（W）出現的位置。KMP 算法把字符匹配的時間復雜度縮小到 O(m+n) ,而空間復雜度也只有O(m)。因為“暴力搜索”的方法會反復回溯主串，導致效率低下，而KMP算法可以利用已經部分匹配這個有效信息，保持主串上的指針不回溯，通過修改子串的指針，讓模式串盡量地移動到有效的位置。 具體算法細節請參考： - **字符串匹配的KMP算法:** http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html - **從頭到尾徹底理解KMP:** https://blog.csdn.net/v_july_v/article/details/7041827 - **如何更好的理解和掌握 KMP 算法?:** https://www.zhihu.com/question/21923021 - **KMP 算法詳細解析:** https://blog.sengxian.com/algorithms/kmp - **圖解 KMP 算法:** http://blog.jobbole.com/76611/ - **汪都能聽懂的KMP字符串匹配算法【雙語字幕】:** https://www.bilibili.com/video/av3246487/?from=search&seid=17173603269940723925 - **KMP字符串匹配算法1:** https://www.bilibili.com/video/av11866460?from=search&seid=12730654434238709250 **除此之外，再來了解一下BM算法！** > BM算法也是一種精確字符串匹配算法，它采用從右向左比較的方法，同時應用到了兩種啟發式規則，即壞字符規則 和好后綴規則 ，來決定向右跳躍的距離。基本思路就是從右往左進行字符匹配，遇到不匹配的字符后從壞字符表和好后綴表找一個最大的右移值，將模式串右移繼續匹配。 《字符串匹配的KMP算法》:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html ## 2. 替換空格 > 劍指offer：請實現一個函數，將一個字符串中的每個空格替換成“%20”。例如，當字符串為We Are Happy.則經過替換之后的字符串為We%20Are%20Happy。 這里我提供了兩種方法：①常規方法；②利用 API 解決。 ```java //https://www.weiweiblog.cn/replacespace/ public class Solution { /** * 第一種方法：常規方法。利用String.charAt(i)以及String.valueOf(char).equals(" " * )遍歷字符串并判斷元素是否為空格。是則替換為"%20",否則不替換 */ public static String replaceSpace(StringBuffer str) { int length = str.length(); // System.out.println("length=" + length); StringBuffer result = new StringBuffer(); for (int i = 0; i < length; i++) { char b = str.charAt(i); if (String.valueOf(b).equals(" ")) { result.append("%20"); } else { result.append(b); } } return result.toString(); } /** * 第二種方法：利用API替換掉所用空格，一行代碼解決問題 */ public static String replaceSpace2(StringBuffer str) { return str.toString().replaceAll("\\s", "%20"); } } ``` ## 3. 最長公共前綴 > Leetcode: 編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。 示例 1: ``` 輸入: ["flower","flow","flight"] 輸出: "fl" ``` 示例 2: ``` 輸入: ["dog","racecar","car"] 輸出: "" 解釋: 輸入不存在公共前綴。 ``` 思路很簡單！先利用Arrays.sort(strs)為數組排序，再將數組第一個元素和最后一個元素的字符從前往后對比即可！ ```java public class Main { public static String replaceSpace(String[] strs) { // 如果檢查值不合法及就返回空串 if (!checkStrs(strs)) { return ""; } // 數組長度 int len = strs.length; // 用于保存結果 StringBuilder res = new StringBuilder(); // 給字符串數組的元素按照升序排序(包含數字的話，數字會排在前面) Arrays.sort(strs); int m = strs[0].length(); int n = strs[len - 1].length(); int num = Math.min(m, n); for (int i = 0; i < num; i++) { if (strs[0].charAt(i) == strs[len - 1].charAt(i)) { res.append(strs[0].charAt(i)); } else break; } return res.toString(); } private static boolean chechStrs(String[] strs) { boolean flag = false; if (strs != null) { // 遍歷strs檢查元素值 for (int i = 0; i < strs.length; i++) { if (strs[i] != null && strs[i].length() != 0) { flag = true; } else { flag = false; break; } } } return flag; } // 測試 public static void main(String[] args) { String[] strs = { "customer", "car", "cat" }; // String[] strs = { "customer", "car", null };//空串 // String[] strs = {};//空串 // String[] strs = null;//空串 System.out.println(Main.replaceSpace(strs));// c } } ``` ## 4. 回文串 ### 4.1. 最長回文串 > LeetCode: 給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構造成的最長的回文串。在構造過程中，請注意區分大小寫。比如`"Aa"`不能當做一個回文字符串。注 意:假設字符串的長度不會超過 1010。 > 回文串：“回文串”是一個正讀和反讀都一樣的字符串，比如“level”或者“noon”等等就是回文串。——百度百科 地址：https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin 示例 1: ``` 輸入: "abccccdd" 輸出: 7 解釋: 我們可以構造的最長的回文串是"dccaccd", 它的長度是 7。 ``` 我們上面已經知道了什么是回文串？現在我們考慮一下可以構成回文串的兩種情況： - 字符出現次數為雙數的組合 - **字符出現次數為偶數的組合+單個字符中出現次數最多且為奇數次的字符** （參見 **[issue665](https://github.com/Snailclimb/JavaGuide/issues/665)** ） 統計字符出現的次數即可，雙數才能構成回文。因為允許中間一個數單獨出現，比如“abcba”，所以如果最后有字母落單，總長度可以加 1。首先將字符串轉變為字符數組。然后遍歷該數組，判斷對應字符是否在hashset中，如果不在就加進去，如果在就讓count++，然后移除該字符！這樣就能找到出現次數為雙數的字符個數。 ```java //https://leetcode-cn.com/problems/longest-palindrome/description/ class Solution { public int longestPalindrome(String s) { if (s.length() == 0) return 0; // 用于存放字符 HashSet<Character> hashset = new HashSet<Character>(); char[] chars = s.toCharArray(); int count = 0; for (int i = 0; i < chars.length; i++) { if (!hashset.contains(chars[i])) {// 如果hashset沒有該字符就保存進去 hashset.add(chars[i]); } else {// 如果有,就讓count++（說明找到了一個成對的字符），然后把該字符移除 hashset.remove(chars[i]); count++; } } return hashset.isEmpty() ? count * 2 : count * 2 + 1; } } ``` ### 4.2. 驗證回文串 > LeetCode: 給定一個字符串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫。 說明：本題中，我們將空字符串定義為有效的回文串。 示例 1: ``` 輸入: "A man, a plan, a canal: Panama" 輸出: true ``` 示例 2: ``` 輸入: "race a car" 輸出: false ``` ```java //https://leetcode-cn.com/problems/valid-palindrome/description/ 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.3. 最長回文子串 > Leetcode: LeetCode: 最長回文子串 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為1000。 示例 1： ``` 輸入: "babad" 輸出: "bab" 注意: "aba"也是一個有效答案。 ``` 示例 2： ``` 輸入: "cbbd" 輸出: "bb" ``` 以某個元素為中心，分別計算偶數長度的回文最大長度和奇數長度的回文最大長度。給大家大致花了個草圖，不要嫌棄！  ```java //https://leetcode-cn.com/problems/longest-palindromic-substring/description/ 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.4. 最長回文子序列 > LeetCode: 最長回文子序列 給定一個字符串s，找到其中最長的回文子序列。可以假設s的最大長度為1000。 **最長回文子序列和上一題最長回文子串的區別是，子串是字符串中連續的一個序列，而子序列是字符串中保持相對位置的字符序列，例如，"bbbb"可以是字符串"bbbab"的子序列但不是子串。** 給定一個字符串s，找到其中最長的回文子序列。可以假設s的最大長度為1000。 示例 1: ``` 輸入: "bbbab" 輸出: 4 ``` 一個可能的最長回文子序列為 "bbbb"。 示例 2: ``` 輸入: "cbbd" 輸出: 2 ``` 一個可能的最長回文子序列為 "bb"。 **動態規劃：** 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]) ```java 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. 括號匹配深度 > 愛奇藝 2018 秋招 Java： >一個合法的括號匹配序列有以下定義: >1. 空串""是一個合法的括號匹配序列 >2. 如果"X"和"Y"都是合法的括號匹配序列,"XY"也是一個合法的括號匹配序列 >3. 如果"X"是一個合法的括號匹配序列,那么"(X)"也是一個合法的括號匹配序列 >4. 每個合法的括號序列都可以由以上規則生成。 > 例如: "","()","()()","((()))"都是合法的括號序列 >對于一個合法的括號序列我們又有以下定義它的深度: >1. 空串""的深度是0 >2. 如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度為max(x,y) >3. 如果"X"的深度是x,那么字符串"(X)"的深度是x+1 > 例如: "()()()"的深度是1,"((()))"的深度是3。牛牛現在給你一個合法的括號序列,需要你計算出其深度。 ``` 輸入描述: 輸入包括一個合法的括號序列s,s長度length(2 ≤ length ≤ 50),序列中只包含'('和')'。 輸出描述: 輸出一個正整數,即這個序列的深度。 ``` 示例： ``` 輸入: (()) 輸出: 2 ``` 思路草圖：  代碼如下： ```java import java.util.Scanner; /** * https://www.nowcoder.com/test/8246651/summary * * @author Snailclimb * @date 2018年9月6日 * @Description: TODO 求給定合法括號序列的深度 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int cnt = 0, max = 0, i; for (i = 0; i < s.length(); ++i) { if (s.charAt(i) == '(') cnt++; else cnt--; max = Math.max(max, cnt); } sc.close(); System.out.println(max); } } ``` ## 6. 把字符串轉換成整數 > 劍指offer: 將一個字符串轉換成一個整數(實現Integer.valueOf(string)的功能，但是string不符合數字要求時返回0)，要求不能使用字符串轉換整數的庫函數。 數值為0或者字符串不是一個合法的數值則返回0。 ```java //https://www.weiweiblog.cn/strtoint/ public class Main { public static int StrToInt(String str) { if (str.length() == 0) return 0; char[] chars = str.toCharArray(); // 判斷是否存在符號位 int flag = 0; if (chars[0] == '+') flag = 1; else if (chars[0] == '-') flag = 2; int start = flag > 0 ? 1 : 0; int res = 0;// 保存結果 for (int i = start; i < chars.length; i++) { if (Character.isDigit(chars[i])) {// 調用Character.isDigit(char)方法判斷是否是數字，是返回True，否則False int temp = chars[i] - '0'; res = res * 10 + temp; } else { return 0; } } return flag != 2 ? res : -res; } public static void main(String[] args) { // TODO Auto-generated method stub String s = "-12312312"; System.out.println("使用庫函數轉換：" + Integer.valueOf(s)); int res = Main.StrToInt(s); System.out.println("使用自己寫的方法轉換：" + res); } } ```