给定一个字符串 s, 找到 s 中最长的回文子串. 你可以假设 s 的最大长度为 1000.
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案.
示例 2:
输入: "cbbd"
输出: "bb"
我的思路是考虑两种情况, 1) 中间为一个数字, 左右关于那个数字对称, 总数为奇数 2) 中间的数字也一样, 总数为偶数个, 但是这两种情况中又要考虑原 sooos 这种情况, 算法不是很优, 我的解法为:
- class Solution {
- public String longestPalindrome(String s) {
- int i, count = 1, p = 1, t;
- int length = s.length();
- boolean flag = false;
- if(length > 0) {
- if (length == 1) return s;
- else if (length > 1) {
- char[] str = s.toCharArray();
- if (length == 2) return str[0] == str[1] ? s : String.valueOf(str[0]);
- else {
- for (i = 1; i < length; i++) {
- if (str[i] == str[i - 1]) {
- if(i != length - 1) {
- if (str[i] == str[i + 1]) {
- if( i == 1 )t = 3;
- else {
- int x = isSymmetry(str, i - 2, i + 1);
- int y = isSymmetry(str, i - 1, i + 1);
- t = x > y?x:y;
- }
- } else t = i == 1 ? 2 : isSymmetry(str, i - 2, i + 1);
- }else t = 2;
- if (count < t) {
- flag = true;
- p = i;
- count = t;
- }
- } else {
- t = isSymmetry(str, i - 1, i + 1);
- if(count < t){
- flag = false;
- p = i;
- count = t;
- }
- }
- }
- if (flag) return count%2 == 0?s.substring(p - count / 2, p + count / 2):s.substring(p - count / 2, p +1+ count / 2);
- else return s.substring(p - count / 2, p +1+ count / 2);
- }
- }
- }
- return null;
- }
- public static int isSymmetry(char[] str, int m, int n){
- int temp = n - m - 1, t;
- if(m >= 0 && n < str.length){
- if(str[m] == str[n]){
- m = m - 1;
- n = n + 1;
- t = isSymmetry(str, m, n);
- return temp > t? temp:t;
- }
- }
- return temp;
- }
- }
我在黑板墙看到一种不用考虑奇偶的情况, 先统计中间相同的数字, 然后左右再考虑是否对称: 该算法为:
- class Solution {
- public String longestPalindrome(String s) {
- if (s == null || s.length() == 0) {
- return "";
- }
- // 保存起始位置, 测试了用数组似乎能比全局变量稍快一点
- int[] range = new int[2];
- char[] str = s.toCharArray();
- for (int i = 0; i <s.length(); i++) {
- // 把回文看成中间的部分全是同一字符, 左右部分相对称
- // 找到下一个与当前字符不同的字符
- i = findLongest(str, i, range);
- }
- return s.substring(range[0], range[1] + 1);
- }
- public static 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;
- }
- }
该算法更为简洁, 且运行速度更快! 果然人外有人, 天外有天!, 学到了, 学到了
来源: http://www.bubuko.com/infodetail-3682080.html