[LeetCode] 5. Longest Palindromic Substring java

2019-11-06 06:19:17

字体：大中小

来源：转载

供稿：网友

/**5. Longest Palindromic Substring * @param s * @returnString 最大回文子串 */ public String longestPalindrome(String s) { if (s == null || s.length() <= 1){ return s; } String ret = ""; int maxLen = 0; for (int i=0, len = s.length(); i<len*2-1; i++) { int left = i/2; int right = i/2+i%2; String curStr = PalindromLength(s, left, right); if (curStr.length() > maxLen) { maxLen = curStr.length(); ret = curStr; } } return ret; } public String PalindromLength(String str, int left, int right) { for (; left>=0 && right < str.length(); left--, right++) { if (str.charAt(left) != str.charAt(right)) { break; } } return str.substring(left+1, right); }

//字符串n，中心为n + n-1(空隙),从每一个中心往两边扫描，O(n^2)

改进：

public String longestPalindrome1(String s) { if (s == null || s.length() == 0) { return ""; } int len = s.length(); boolean[][] palin = new boolean[len][len]; String res = ""; int maxlen = 0; for (int i = len-1; i >= 0; i--) { for (int j = i; j < len; j++) { if (s.charAt(i) == s.charAt(j) && (j-i<=2 || palin[i+1][j-1])) { palin[i][j] = true; if (maxlen < j-i+1) { maxlen = j-i+1; res = s.substring(i,j+1); } } } } return res; }

//动态规划，申请额外空间存储i~j是否回文

上一篇：[LeetCode] 10. Regular Expression Matching java

下一篇：[LeetCode] 67. Add Binary java