leetCode 005 最长回文

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例输入输出：

  1. 输入：s = "babad"
  2. 输出："bab"
  3. 解释："aba" 同样是符合题意的答案。
  5. 输入：s = "cbbd"
  6. 输出："bb"
  8. 输入：s = "a"
  9. 输出："a"
  11. 输入：s = "ac"
  12. 输出："a"

思路：

中心向两边遍历

  • 每一个字符都视为“中心”，向左右扩张，如果左右相等再向左右扩张

  • 参数：

    • 最长长度len；返回的字符串开始位置start；回文计算的左右指针l和r；回文计算返回长度cur。

  • 终止条件：

    • s.charAt(s.length())，即遍历到字符串的最后一个元素。

  • 迭代过程中做的事：

    • 计算该位置的最大回文长度，由于可能是奇数回文（bab）和偶数回文（baab），所以要计算两次，lr分别问i，i和i，i+1。

    • 在找回文时，继续迭代，找到最长回文，返回与另一迭代比较，大的当作本次找到最长回文，记为cur。

      • 此时需要注意，l与r均是越界的，实际情况是回文长度=r-l-1

    • 如果cur比之前的len大：

      • 将cur作为新的len。
      • 与此同时，start重新计算，位置是本次位置-最大长度/2，为了避免奇数回文导致错误情况发生，cur需要-1.

  • 复杂度分析：

    • 时间复杂度：最坏情况全为同一个字符，O（N^2）。
    • 空间复杂度：O(N)。

  • 代码：

  • class Solution {
  public String longestPalindrome(String s) {
      int len = 0;
      int start = 0;
      for(int i = 0; i < s.length(); i++){
          int cur = Math.max(getLength(s,i,i),getLength(s,i,i+1));
          if(cur > len){
              len = cur;
              start = i - (cur-1)/2;
          }
      }
      return s.substring(start, start + len);
  }

  private int getLength(String s, int l, int r){
      while(l >= 0 && r < s.length()
              && s.charAt(l) == s.charAt(r)){
          l--;
          r++;
      }
      return r-l-1;
  }
}