Solutions of Longest Palindromic Substring

suffix tree
public class Solution { public String longestPalindrome(String s) { if (s.length() <= 1) return s; String result = ""; Node root = new Node(); // original string for (int i = 0; i < s.length(); i++) { String subString = s.substring(i); Node node = root; for(int j = 0; j < subString.length(); j++) { if (node.nodeList.get(subString.charAt(j)) == null) { Node leaf = new Node(); leaf.letter = subString.charAt(j); leaf.isOriginal = 1; node.nodeList.put(subString.charAt(j), leaf); } else { node.nodeList.get(subString.charAt(j)).isOriginal = 1; } node = node.nodeList.get(subString.charAt(j)); } } // reversed string String rs = new StringBuilder(s).reverse().toString(); for (int i = 0; i < rs.length(); i++) { String subReversedString = rs.substring(i); Node node = root; String tmpString = ""; for(int j = 0; j < subReversedString.length(); j++) { if (node.nodeList.get(subReversedString.charAt(j)) == null) { Node leaf = new Node(); leaf.letter = subReversedString.charAt(j); leaf.isOriginal = 0; node.nodeList.put(subReversedString.charAt(j), leaf); } else { // target node exists, and which is generated by the original string. if (node.nodeList.get(subReversedString.charAt(j)).isOriginal == 1) { tmpString += subReversedString.charAt(j); } } node = node.nodeList.get(subReversedString.charAt(j)); } if (tmpString.length() > result.length()) { result = tmpString; } } return result; } } class Node { char letter; int isOriginal; Map<Character, Node> nodeList = new HashMap<>(); }
normal
public class Solution { public String longestPalindrome(String s) { int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; } }
manacher’s algorithm
public class Solution { public String longestPalindrome(String s) { if (s.length() <= 2) return s; String separator = "@", starter = "^"; StringBuilder stringBuilder = new StringBuilder(starter).append(separator); for (int i = 0; i < s.length(); i++) { stringBuilder.append(s.charAt(i)).append(separator); } String formattedString = stringBuilder.toString(); int[] result = new int[formattedString.length()]; // id stands for **the center of furthest palindrome string** // mx stands for **the right boundary of furthest palindrome string** int mx = 0, id = 0; for (int i = 1; i < formattedString.length(); i++) { if (mx > i) { result[i] = result[2*id - i] > mx - i ? mx - i : result[2*id - i]; } else { result[i] = 1; } while ((i + result[i]) < formattedString.length() && (i - result[i]) >= 0 && formattedString.charAt(i + result[i]) == formattedString.charAt(i - result[i])) { result[i]++; } if (i + result[i] > mx) { mx = i + result[i]; id = i; } } int maxIndex = 0, maxValue = 0; for (int k = 0; k < formattedString.length(); k++) { if (result[k] > maxValue) { maxIndex = k; maxValue = result[k]; } } return formattedString .substring(maxIndex - result[maxIndex] + 1, maxIndex + result[maxIndex] - 1) .replace(separator, ""); } }
DP
public class Solution { public String longestPalindrome(String s) { if (s.length() <= 2) return s; int start = 0, end = 0; // matrix[x][y] stands for if s.substring(x, y + 1) is a palindrome string boolean matrix[][] = new boolean[s.length()][s.length()]; for (int y = 1; y < s.length(); y++) { int x = 0; matrix[y][y] = true; while (x < y) { if (s.charAt(x) == s.charAt(y)) { if ((y - x == 1) || matrix[x + 1][y - 1]) { // is palindrome matrix[x][y] = true; // compare if (y - x + 1 > end - start + 1) { start = x; end = y; } } } x++; } } return s.substring(start, end + 1); } }
Reference: