0%

leetcode之旅-05-最长回文字串

Posted on In

1. 题目描述（中等题目）

题目描述

  • 就是查找字符串中最长的一个回文字串，结果唯一

    2 我的解法

    思路：暴力解法，滑动窗口。从大到小查找，每一个窗口的内容都判断是否时回文，是，就直接返回结果。这样做保证返回的最长回文字串之一。
    1
    //题目思路是 设置滑动窗口，从大到小查找
    2
    class Solution {
    3
        public boolean isPalindromic(String s,int start,int end)
    4
        {
    5
            while(start<end)
    6
                if (s.charAt(start++)!= s.charAt(end--))
    7
                    return false;
    8
            return true;
    9
        }
    10
        public String longestPalindrome(String s) {
    11
            int n = s.length();
    12
            if(n==0)//注意判空
    13
                return "";
    14
            for(int w=n ; w>1 ; w--)//窗口大小
    15
            {
    16
               for(int i=0,j=i+w-1;j<n&&i<n;i++,j++)
    17
                {
    18
                    if(isPalindromic(s,i,j))
    19
                        return s.substring(i,j+1);
    20
                }
    21
            }
    22
            return String.valueOf(s.charAt(0));
    23
        }
    24
    }
  • 时间复杂度：最坏O($n^3$)。主函数与两层循环，每次循环的最大值都是n，所以是$n^2$，在判断回文串时，最大值是n，所以一共O($n^3$)
  • 空间复杂度：O(1)