LeetCode 5. Longest Palindromic Substring (Java)

tags: leetcode Java Palindromic

Description

Given a string s, return the longest palindromic substring in s.

給定一個String，並找出最長的回文子字串（palindromic substring），如有多個相同長度的最長子字串可只回傳一個

Example

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "ac"
Output: "a"

Idea

• Approach 1 暴力法
  • 先用雙迴圈找出每組substring，時間複雜度為
    $O(n^2)$
  • 再將每組找出的substring測試是否為迴文，時間複雜度
    $O(n)$
  • 總共時間複雜度為
    $O(n^3)$，無法處理過長字串，Leetcode因處理時間太長無法通過
• Approach 2
  • 如果一個迴文子字串，其中心不是回文，那這串子字串絕對不是回文
  • 使用外迴圈遍歷字串中的每個字元，內迴圈在用兩個指標start和end以往外擴展
  • 因為會有奇偶數問題，所以內迴圈分成兩組分別處理
  • 總時間複雜度為
    $O(n^2)$，空間複雜度為
    $O(1)$

Code

Approach 1

class Solution {
    public String longestPalindrome(String s) {
        //if(s.length() == 1) return s;        
        int len = s.length();
        String result = new String();
        int max_length = 0;
        for (int i = 0;i < len;i++){
            for (int j = i;j < len;j++){
                String ss = s.substring(i, j+1);
                boolean isPal = true;
                for (int z = 0; z < ss.length(); z++){
                    if(ss.charAt(z) != ss.charAt(ss.length()-z-1)){
                        isPal = false;
                        break;
                    }
                }
                if(isPal && ss.length() > max_length){
                    max_length = ss.length();
                    result = ss;
                }
                
            }
        }
        return result;
    }
}

我寫完此寫法後，因為執行時間過長導致Time Limit Exceeded，所以又找了其他方法，將Big-O變小

Approach 2

class Solution {
    public String longestPalindrome(String s) {      
        int len = s.length();
        String result = new String();
        int max_length = 0;
        for (int i = 0;i < len;i++){ 
            //center odd
            
            for (int start = i, end = i; start >= 0 && end < len;start--,end++){
                if(s.charAt(start) != s.charAt(end))//判斷前後是否一致
                    break; //不一致的話就不是回文，跳出迴圈
                if(end - start + 1 > max_length){ //檢查此次的回文子字串是否為最長的
                    max_length = end - start + 1;
                    result = s.substring(start, end+1);//將此子字串放到result
                }
            }
            //center even
            
            for (int start = i, end = i+1; start >= 0 && end < len;start--,end++){
                //因為考慮到會有偶數的子字串(ex.cbbc)所以end在初始就往右一格或start往左一格都可
                if(s.charAt(start) != s.charAt(end))
                    break;   
                if(end - start + 1 > max_length){
                    max_length = end - start + 1;
                    result = s.substring(start, end+1);
                }
            }
        }
        return result;
    }
}

Result (Approach 2)

Runtime: 28 ms, faster than 57.01% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 39.6 MB, less than 44.91% of Java online submissions for Longest Palindromic Substring.