新增扩散法解决最长回文子串问题

dai · dai · commit f6c16cd70993 · 2021-03-31T15:29:53.000+08:00
diff --git a/27-算法面试专题-字符串.md b/27-算法面试专题-字符串.md
@@ -215,5 +215,68 @@ public class StringUtil {
         return len;
     }
 
+
+    /**
+     * 7、最长回文子串问题。
+     * 该解法是扩散法。时间复杂度为O(N * N)。(最优解是马拉车算法，可以优化该题到O(N)，不掌握)
+     * @param s
+     * @return
+     */
+    public static String longestPalindrome2(String s) {
+
+        if(s.length() == 0) {
+            return s;
+        }
+
+        // 全局最大回文长度
+        int res = 1;
+        // 全局最大回文长度对应的左位置
+        int ll = 0;
+        // 全局最大回文长度对应的右位置
+        int rr = 0;
+
+
+        for (int i = 0; i < s.length(); i++) {
+
+            // 以i为下标的奇数情况，是否有更大的len来更新res
+            int l = i - 1;
+            int r = i + 1;
+
+            // l和r都在合法范围。且l和r位置字符相等，可以继续扩散
+            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
+                int len = (r - l + 1);
+                // 更新最长回文串的长度
+                if(len > res) {
+                    res = len;
+                    ll = l;
+                    rr = r;
+                }
+                // 扩散
+                l--;
+                r++;
+            }
+
+            // 以i为下标偶数的情况。是否有更大的len来更新全局res
+            l = i;
+            r = i + 1;
+            // l和r都在合法范围。且l和r位置字符相等，可以继续扩散
+            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
+                int len = (r - l + 1);
+                // 更新最长回文串的长度
+                if(len > res) {
+                    res = len;
+                    ll = l;
+                    rr = r;
+                }
+                // 扩散
+                l--;
+                r++;
+            }
+
+        }
+
+        return s.substring(ll, rr + 1);
+    }
+
 }
 ```
