欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Longest Palindromic Substring(最长回文)

程序员文章站 2024-02-24 17:51:58
...

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: "bb

 /**
     * 暴力**:遍历截取字符串,并将截取到的字符串进行反转,与原字符串相比是否相等
     * 如果相等则是回文,直到找到长度最大的回文字符串为止
     * @param s
     * @return
     */
    public static String LongestPalindromicSubstring1(String s)
    {
        if(s.length() == 0 || s == null)  return "";
        if(s.length() < 2)   return s;
        String temp1 = null;
        String temp2 = null;
        String result = s.substring(0,1);
        for(int i =0; i < s.length();i++)
        {
            temp1 = null;
            temp2 = null;
            for(int j = s.length(); j>=i;j--)
            {
                if(j-i<result.length()) break;
                temp1 = s.substring(i,j);
                temp2 = new StringBuilder(temp1).reverse().toString();
                if(temp1.equals(temp2)&&temp1.length() > result.length())
                    result = temp1;
            }
        }
        return result;
    }

    /**
     * 动态规划:记录前面的字符串是否为回文,是则保存为True,反之则保存为false。
     * 在进入下一次判断时,如果首尾两个字符串相等,则只需判断它相邻的字符串是否为回文即可。
     * abcba:在进行到a  a 时,只需比较bcb是否为回文。
     * 因此,需要一个二维boolean数组来保存某一字符串是否为回文
     * @param s
     * @return
     */
    public static String LongestPalindromicSubstring2(String s)
    {
        if (s.length() == 0 || s == null)  return "";
        if(s.length() < 2)   return s;
        boolean [][] temp = new boolean[s.length()][s.length()];
        String result = s.substring(0,1);
        for(int i = 0; i < s.length(); i++)
        {
            for(int j = 0; j <= i;j++)
            {
                temp[j][i] = s.charAt(i) == s.charAt(j) &&(i-j <=2 || temp[j+1][i-1]);
                if(temp[j][i])
                {
                    if(i-j+1 > result.length())
                    {
                        result = s.substring(j,i+1);
                    }
                }
            }
        }
        return result;
    }

    /**
     * 中心扩展算法,一个字符串中存在有两个中心的情况,因此ExpandAroundCenter需要执行两次
     * @param s
     * @return
     */
    public static String LongestPalindromicSubstring3(String s)
    {
        if(s.length() ==0 || s == null)  return "";
        if(s.length() < 2)  return s;
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.length()-1; i++)
        {
            int len1 = ExpandAroundCenter(s,i,i);
            int len2 = ExpandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len > end-start)
            {
                start = i- (len -1) /2;//回到起始点
                end = i+ len / 2; //回到结束位置
            }

        }
        return s.substring(start,end+1);
    }

    /**
     * 以某一位置为中心向两边扩展
     * @param s
     * @param left
     * @param right
     * @return
     */
    public static int ExpandAroundCenter(String s, int left, int right)
    {
        int L = left;
        int R = right;
        while(L >=0 && R < s.length() && s.charAt(L) == s.charAt(R))
        {
            L--;
            R++;
        }
        return R-L-1;
    }

   static StringBuilder longest = new StringBuilder("");

    /**
     * 中心扩展算法的另一种写法
     * @param s
     * @return
     */
    public static String LongestPalindromicSubstring4(String s)
    {
        if (s.length() <= 1) return s;

        for (int i = 0; i < s.length(); i++) {
            expand(s, longest, i, i); //odd
            expand(s, longest, i, i + 1); //even
        }

        return longest.toString();
    }
    private static void expand(String s, StringBuilder longest, int i, int j) {
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i + 1 > longest.length()) {
                    //删除longest原有的字符串
                    longest.delete(0, longest.length());
                    //重新向longest中添加字符串
                    longest.append(s.substring(i, j + 1));
                }
                //向两边扩展
                i--;
                j++;
            }
            else
                break;
        }
    }