OR博客
5. 最长回文子串
OrdinaryRoad
创建于:2023-05-14 16:59:10
更新于:2023-05-14 17:00:58
新疆
0
10
58
0
#### [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) 给你一个字符串** **`s`,找到** **`s` 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 **示例 1:** <pre><strong>输入:</strong>s = "babad" <strong>输出:</strong>"bab" <strong>解释:</strong>"aba" 同样是符合题意的答案。 </pre> **示例 2:** <pre><strong>输入:</strong>s = "cbbd" <strong>输出:</strong>"bb" </pre> **提示:** * `1 <= s.length <= 1000` * `s` 仅由数字和英文字母组成 --- ### 解题思路 暴力法胡乱分析一通... ![分析过程](https://ordinaryroad.xyz:444/api/upms/file/download/ordinaryroad-blog/2023-05-14/33b806b3149d457896720ca88653d171.png) ### 代码 ```java /** * 5. 最长回文子串 * 242ms 43MB * * @author mjz * @date 2023/5/14 */ class Solution { public static String longestPalindrome(String s) { String result = s.isEmpty() ? s : s.substring(0, 1); int s_length = s.length(); for (int i = 0; i < s_length; i++) { int low = i, high = s_length - 1; while (high > low) { // 可能的长度比当前的小,直接结束 if (result.length() + i + 1 > s_length) { // System.out.println("可能的长度比当前的小,直接结束 " + (s_length - i - 1)); return result; } while (high > low && s.charAt(high) != s.charAt(low)) { high--; } int length = high - low + 1; if (length <= 0) { break; } String substring = s.substring(i, i + length); // 可能的长度小于result才尝试判断 boolean palindrome = isPalindrome(s, i, i + length - 1); if (palindrome) { // System.out.println("result.length() < length = " + (result.length() < length)); if (result.length() < length) { // System.out.println("找到回文:" + substring); result = substring; } // 找到后肯定是当前这一轮的最大值,直接进入下一轮 break; } else { high--; } } } return result; } public static boolean isPalindrome(String string, int startIndex, int endIndex) { while (endIndex >= startIndex && string.charAt(startIndex) == string.charAt(endIndex)) { startIndex++; endIndex--; } return endIndex <= startIndex; } } ```
评论