LeetCode - 5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

 

---

문제

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"

---

String 을 받아서 String을 리턴해야 한다.

Palindrome String: S = reverse S 가 같아야 한다.

 

가능한 경우중 제일 긴 Palindrom 을 찾아야 한다.

 

Java 는 String 이 imuutable 하기 때문에 s.subString(i , j) 이 O(j-i) 만큼 시간이 걸리게 된다.

 

그래서 첫번째 시도했던 아래 코드는 Time Limit Exceed 가 걸렸다.

import java.util.*;
class Solution {
    public String longestPalindrome(String s) {
        String answer = "";
        int len = s.length();
        for(int i = len ; i > 0 ; i--){
            int comparesize = i;
            // System.out.println(i);
            
            for(int j = 0 ; j < len ; j++){
                int head = j;
                int tail = j+i;
                 if(tail > len){
                    break;
                }
                
                String temp = s.substring(head,tail);
                // System.out.println(head + " : " + tail);
                // System.out.println(temp);
                if( isPalindrom(temp)){
                    if(answer.length() < temp.length()){
                        answer = temp;
                    }
                }
               
            }
        }
        
        return answer;   
    }
    
    public boolean isPalindrom(String str){
        for(int i = 0; i<str.length()/2; i++){
            int compIdx = str.length()-i-1;
            if(str.charAt(i) == (str.charAt(compIdx)) == false){                                                            
                return false;
            }
        }
        return true;
    }
}

---

 

길이가 홀수와 짝수일 때를 나누어서 생각해서

1 2 3 4 5 

에서 뭐 3 이면 2 4 비교 1 5 비교 이렇게 하다가 팰린드롬이 아니면 break 하는 방식으로 해도 Time Limit 걸린다.

 

또한 abb 와 같이 짝수 길이 팰린드롬 bb 못찾는다. 하 진짜

 

class Solution {
    public String longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        String answer = "";
        
        if(s.length() == 1){
            return s;
        }
        if(s.length() == 2){
            if(s.charAt(0) == s.charAt(1)){
                return s;
            }else{
                return String.valueOf(s.charAt(0));
            }
        }

        //odd number
        if (s.length() % 2 == 1) {
            for (int index = 0; index < s.length(); index++) {
                int len = 0;
                while (true) {
                    int head = index - len;
                    int tail = index + len;
                    if (head < 0 || tail > s.length() - 1) {
                        break;
                    }
                    System.out.println(head + " : " + tail);
                    if (head == tail) {
                        System.out.println(arr[head]);
                    } else {
                        if (arr[head] == arr[tail]) {
                            String temp = "";
                            for (int i = head; i < tail + 1; i++) {
                                temp = temp + arr[i];
                            }
                            System.out.print(temp);
                            if (temp.length() > answer.length()) {
                                answer = temp;
                            }

                        } else {
                            break;
                        }

                    }
                    System.out.println();
                    len++;

                }
            }
        } else {
            //even number
            for (int index = 0; index < s.length(); index++) {
                int len = 0;
                while (true) {
                    int head = index;
                    int tail = index + len;
                    if (head < 0 || tail > s.length() - 1) {
                        break;
                    }
                    // System.out.println(head + " : " + tail);
                    if (head == tail) {
                        // System.out.println(arr[head]);
                    } else {
                        if (arr[head] == arr[tail]) {
                            String temp = "";
                            for (int i = head; i < tail + 1; i++) {
                                temp = temp + arr[i];
                            }
                            // System.out.print(temp);
                            if (temp.length() > answer.length()) {
                                answer = temp;
                            }

                        } else {
                            break;
                        }

                    }
                    // System.out.println();
                    len++;

                }
            }
        }


        return answer;
    }
}

 

---

문자열 저장하지 말고 시작하는 index 와 팰린드롬이 성립되는 길이값을 비교하여 찾아 본다.

 

class Solution {
    
    int index, maxLen;
    
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len<2){
            return s;
        }
        
        for(int i = 0 ; i  < len - 1 ; i++){
            find(s,i,i);
            find(s,i,i+1);
        }
        return s.substring(index,index+maxLen);
        
    }
    
    public void find(String s, int i, int j){
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        if(maxLen < j-i-1){
            index = i+1;
            maxLen = j - i -1;
        }
    }
}