题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
代码
暴力匹配
- 时间复杂度 O(N^3)
- 空间复杂度 O(1)
public String longestPalindrome(String str) { int n = str.length(); if (n < 2) { return str; } int maxLen = 1; int begin = 0; char[] charArray = str.toCharArray(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) { maxLen = j - i + 1; begin = i; } } } return str.substring(begin, begin + maxLen); } private boolean validPalindromic(char[] charArray, int left, int right) { while (left < right) { if (charArray[left] != charArray[right]) { return false; } left++; right--; } return true; }
动态规划
- 时间复杂度 O(N^2)
- 空间复杂度 O(N^2)
public String longestPalindrome(String str) { int n = str.length(); if (n < 2) { return str; } int maxLen = 1; int begin = 0; char[] charArray = str.toCharArray(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) dp[i][i] = true; for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { if (charArray[i] != charArray[j]) dp[i][j] = false; else { if (j - i < 3) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } } if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } return str.substring(begin, begin + maxLen); }
中心扩散法
- 时间复杂度 O(N^2)
- 空间复杂度 O(1)
public String longestPalindrome(String str) { int n = str.length(); if (n < 2) { return str; } int maxLen = 1; String res = str.substring(0, 1); for (int i = 0; i < n - 1; i++) { String oddStr = centerSpread(str, i, i); String evenStr = centerSpread(str, i, i + 1); String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr; if (maxLenStr.length() > maxLen) { maxLen = maxLenStr.length(); res = maxLenStr; } } return res; } private String centerSpread(String s, int left, int right) { int len = s.length(); int i = left, j = right; while (i >= 0 && j < len) { if (s.charAt(i) == s.charAt(j)) { i--; j++; } else { break; } } return s.substring(i + 1, j); }
中心扩散法的改进
public String longestPalindrome(String str) { if (str == null || str.length() < 1) return ""; if (str.length() == 1) return str; int[] range = new int[2]; char[] arr = str.toCharArray(); for (int i = 0; i < arr.length; i++) { i = findLongest(arr, i, range); } return str.substring(range[0], range[1] + 1); } private int findLongest(char[] str, int low, int[] range) { int high = low; while (high < str.length - 1 && str[high + 1] == str[low]) high++; int ans = high; while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) { low--; high++; } if (high - low > range[1] - range[0]) { range[0] = low; range[1] = high; } return ans; }