LeetCode：最長回文字串

No.5 最長回文字串

利用公共子串、動態規劃查詢字串的最長回文子串

題目:

給定一個字串 s，找到 s 中最長的回文子串，你可以假設 s 的最大長度為 1000

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案，

示例 2：

輸入: "cbbd"
輸出: "bb"

解法：

1. 列舉法

   列舉字串并判斷是否回文

   時間復雜度：\(O(n^3)\)

   空間復雜度：\(O(1)\)

   class Solution
   {
       public String longestPalindrome(String s)
       {
           int len = s.length();
           int max = 0;
           String ans = "";
           for (int i = 0; i < len; i++)
           {
               for (int j = i + 1; j <= len; j++)
               {
                   String str = s.substring(i, j);
                   if (isPalindromic(str) && str.length() > max)
                   {
                       max = Math.max(max, str.length());
                       ans = str;
                   }
               }
           }
           return ans;
       }
   
       public boolean isPalindromic(String s)
       {
           int len = s.length();
           for (int i = 0; i < len / 2; i++)
           {
               if (s.charAt(i) != s.charAt(len - i - 1))
               {
                   return false;
               }
           }
           return true;
       }
   }
   
   

2. 公共子串、動態規劃

   時間復雜度：\(O(n^2)\)

   空間復雜度：\(O(n^2)\)

class Solution
{
   
    public String longestPalindrome(String s)
    {
        if (s.equals(""))
        {
            return "";
        }
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString();//字串倒置
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++)
        {
            for (int j = 0; j < length; j++)
            {
                if (origin.charAt(i) == reverse.charAt(j))
                {
                    if (i == 0 || j == 0)
                    {
                        arr[i][j] = 1;
                    }
                    else
                    {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen)
                {
                    int beforeRev = length - 1 - j;
                    if (beforeRev + arr[i][j] - 1 == i)
                    { //判斷下標是否對應
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }
}

3. 中心擴散

   長度分偶數和奇數，每個位置兩種遍歷方式

   時間復雜度：\(O(n^2)\)

   空間復雜度：\(O(1)\)

   class Solution
   {
       public String longestPalindrome(String s)
       {
           int sLen = s.length();
           if (sLen < 2) return s;
           int start = 0, end = 0;
           for (int i = 0; i < sLen; i++)
           {
               int len1 = getLength(s, i, i);
               int len2 = getLength(s, i, i + 1);
               int maxLen = Math.max(len1, len2);
               if (maxLen > end - start + 1)
               {
                   start = i - (maxLen - 1) / 2;
                   end = i + maxLen / 2;
               }
           }
           return s.substring(start, end + 1);
       }
   
       public int getLength(String s, int l, int r)
       {
           int len = s.length();
           while (l >= 0 && r < len && s.charAt(l) == s.charAt(r))
           {
               l--;
               r++;
           }
           return r - l - 1;//開區間內的字符數=右-左-1
       }
   }
   

標籤：其他

上一篇：LeetCode：無重復字符的最長子串

下一篇：二叉樹的鏡像