LeetCode #5

问题：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

思路：暴破

package xyz.quxiao.play.lab.leetcode;

/**
 * 给定字符串，查找最长回文 "babad" -> "bab"或"aba"; "cbbd" -> "bb" * * @author 作者 :quxiao 创建时间：2017/11/14 20:17
 */public class Problem5 {

  public static void main(String[] args) {
    run("babad");
    run("cbbd");
  }

  public static void run(String s) {
    System.out.println(s + ": " + longestPalindrome(s));
  }

  // 思路：暴破，i从0到最后，以i为奇数中心和偶数左边分别查找
  public static String longestPalindrome(String s) {
    int total = s.length();
    String ret = "";
    for (int i = 0; i < total; i++) {
      String odd = findPalindromeOdd(s, i);
      String even = findPalindromeEven(s, i);
      if (odd.length() > ret.length()) {
        ret = odd;
      }
      if (even != null && even.length() > ret.length()) {
        ret = even;
      }
    }
    return ret;
  }

  // 以idx为中心
  public static String findPalindromeOdd(String s, int idx) {
    int size = s.length();
    int start = idx - 1;
    int end = idx + 1;
    while (start >= 0 && end < size && s.charAt(start) == s.charAt(end)) {
      --start;
      ++end;
    }
    return s.substring(++start, end);
  }

  // 以idx和idx+1为中心
  public static String findPalindromeEven(String s, int idx) {
    int size = s.length();
    int comp = idx + 1;
    if (comp < size) {
      if (s.charAt(idx) == s.charAt(comp)) {
        int start = idx - 1;
        int end = idx + 2;
        while (start >= 0 && end < size && s.charAt(start) == s.charAt(end)) {
          start--;
          end++;
        }
        return s.substring(start + 1, end);
      } else {
        return null;
      }
    } else {
      return null;
    }
  }
}