5. 最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
public String longestPalindrome(String s) { int center = 0; int rightSide = 0; int index = 0; int radius = 0; StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("@"); for (int i = 0; i < s.length(); i++) { stringBuilder.append(s.charAt(i)); stringBuilder.append("@"); } String newString = stringBuilder.toString(); int[] ints = new int[newString.length()]; for (int i = 0; i < ints.length; i++) { if (rightSide > i) { int left = 2 * center - i; ints[i] = ints[left]; if (ints[left] + i < rightSide) { ints[i] = ints[left]; continue; } else { ints[i] = rightSide - i; } } while (i - ints[i] - 1 >= 0 && i + ints[i] + 1 < ints.length) { if (newString.charAt(i - ints[i] - 1) == newString.charAt(i + ints[i] + 1)) { ints[i]++; } else { break; } } rightSide = i + ints[i]; center = i; if (radius < ints[i]) { radius = ints[i]; index = i; } } StringBuffer sb = new StringBuffer(); for (int i = index - radius + 1; i <= index + radius; i += 2) { sb.append(newString.charAt(i)); } return sb.toString(); }
|
问题: CCC 是cc
近期评论