feat: update 005

Blankj · Blankj · commit 5765dbc6301e · 2017-11-06T18:24:20.000+08:00
diff --git a/note/005/README.md b/note/005/README.md
@@ -62,10 +62,12 @@ class Solution {
 ## 思路1
 
 如果利用暴力法遍历所有字串是否回文的情况这道题肯定是 `Time Limit Exceeded` 的，那么我们是否可以把之前遍历的结果利用上呢，那么动态规划的想法就呼之欲出了，我们定义 `dp[i][j]` 的意思为字符串区间`[i, j]`是否为回文串，那么我们分三种情况：
+
 1. 当 `i == j` 时，那么毫无疑问 `dp[i][j] = true`；
 2. 当 `i + 1 == j` 时，那么 `dp[i][j]` 的值取决于 `s[i] == s[j]`；
 3. 当 `i + 1 < j` 时，那么 `dp[i][j]` 的值取决于 `dp[i + 1][j - 1] && s[i] == s[j]`；
-根据以上的动态转移方程，我们的问题即可迎刃而解，时间复杂度的话很显而易见，也是 `O(n^2)`。
+
+根据以上的动态转移方程，我们的问题即可迎刃而解，时间复杂度的话显而易见，也是 `O(n^2)`。
 
 ```java
 class Solution {
@@ -97,7 +99,32 @@ class Solution {
 
 ## 思路2
 
-最后一种思路那就是 `Manacher's Algorithm`，中文名叫马拉车算法，该算法就是专为解决此问题而发明的。
+马拉车算法(Manacher's Algorithm)
+
+## 背景
+
+给定一个字符串，求出其最长回文子串。例如：
+
+1. s = "babad"，最长回文长度为 `3`，可以是 `bab` 或者 `aba`；
+2. s = "cbbda"，最长回文长度为 `2`，即 `bb`；
+3. s = "abcde"，最长回文长度为 `1`，即单个字符本身。
+
+等同于LeetCode上的第五题：[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)
+
+其相关题解可以查看这里：[传送门](https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md)
+
+以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为 `O(n2)`，效率很差。
+
+1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 `O(n)`。下面来看看马拉车算法是如何工作的。
+
+最后一种思路那就是 `Manacher's Algorithm`，中文名叫马拉车算法，该算法就是专为解决此问题而发明的，其时间复杂度提升到了线性。下面我以我理解的思路来讲解其原理。
+由于回文串的奇偶行不确定，比如 `lol` 是奇回文，而 `lool` 是偶回文，马拉车算法的第一步就是对其进行预处理，做法就是在每个字符两侧都加上一个特殊字符，一般就是不会出现在原串中的即可，我们可以选取 `#`，那么
+
+`lol` -> `#l#o#l#`
+`lool` -> `#l#o#o#l#`
+
+这样处理后不管原来字符串长度是奇还是偶，最终得到的长度都将是奇数，这样就能把两种情况合并起来考虑。
+
 
 
 ## 结语
diff --git a/src/com/blankj/medium/_005/Solution.java b/src/com/blankj/medium/_005/Solution.java
@@ -33,34 +33,40 @@ public class Solution {
 //            st = l + 1;
 //            end = r - 1;
 //        }
+//    }
+
+//    public String longestPalindrome(String s) {
+//        int len = s.length();
+//        if (len <= 1) return s;
+//        int st = 0, end = 0;
+//        char[] chars = s.toCharArray();
+//        boolean[][] dp = new boolean[len][len];
+//        for (int i = 0; i < len; i++) {
+//            dp[i][i] = true;
+//            for (int j = 0; j < i; j++) {
+//                if (j + 1 == i) {
+//                    dp[j][i] = chars[j] == chars[i];
+//                } else {
+//                    dp[j][i] = dp[j + 1][i - 1] && chars[j] == chars[i];
+//                }
+//                if (dp[j][i] && i - j > end - st) {
+//                    st = j;
+//                    end = i;
+//                }
+//            }
+//        }
+//        return s.substring(st, end + 1);
 //    }
 
     public String longestPalindrome(String s) {
-        int len = s.length();
-        if (len <= 1) return s;
-        int st = 0, end = 0;
-        char[] chars = s.toCharArray();
-        boolean[][] dp = new boolean[len][len];
-        for (int i = 0; i < len; i++) {
-            dp[i][i] = true;
-            for (int j = 0; j < i; j++) {
-                if (j + 1 == i) {
-                    dp[j][i] = chars[j] == chars[i];
-                } else {
-                    dp[j][i] = dp[j + 1][i - 1] && chars[j] == chars[i];
-                }
-                if (dp[j][i] && i - j > end - st) {
-                    st = j;
-                    end = i;
-                }
-            }
-        }
-        return s.substring(st, end + 1);
+
+        return s;
     }
 
     public static void main(String[] args) {
         Solution solution = new Solution();
         System.out.println(solution.longestPalindrome("babad"));
         System.out.println(solution.longestPalindrome("cbbd"));
+
     }
 }
