[알고리즘] Leetcode_5_Longest_Palindromic_Substring

Problem

Solve

class Solution {
    public boolean isPalindrome(String s){
        int left = 0, right = s.length()-1;
        while(left <= right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
        }
        return true;
    }
    public String longestPalindrome(String s) {
    String longest = "";
        
        //substring 만들기
        for(int i = 0 ; i < s.length() ; i++){
            String newStr = "";
            for(int j = i ; j < s.length() ; j++){
                newStr += s.charAt(j);
                System.out.println("만들 수 있는 substring : "+ newStr);
                if(isPalindrom(newStr)){
                    System.out.println("회문임!");
                    if(longest.length() < newStr.length()){
                        longest = newStr;
                    }
                    System.out.println("이 때 longest 는 "+longest);
                }
            }
        }

        return longest;
     }
}

이런 식으로 substring 을 조합해서 회문인지 여부를 판단하고 그 중 가장 긴 회문을 리턴하는 방식이다. 하지만 이것은 O(n^2) * n = O(n^3) 이라 time Limit 에 걸리고 만다.

class Solutioin {
    public static boolean isPalindrom(String s){
        int left = 0, right = s.length()-1;
        //회문인지 아닌지 판별
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public static String longestPalindrome(String s) {
 		String longest = "";

        for(int i = 0 ; i <s.length() ; i++){
            System.out.println("i:"+i);
            String odd = getPalindrome(s, i,i);
            if(odd.length() > longest.length()) longest = odd;

            String even = getPalindrome(s, i, i+1);
            if(even.length() > longest.length()) longest = odd;


            System.out.println("odd: "+odd+" even: "+ even + " longest: "+longest);
        }
        
        return longest;
    }

회문판별하는 것은 같은데 이제 substring 조합하는 부분에서 two pointer 를 쓴다. 해당 i 번째 문자에서 양쪽으로 퍼져나가는 형식으로 substring 을 만들어서 회문인지를 판별하면 O(n^2)가 되어서 훨씬 시간복잡도를 줄일 수 있다.

근데 이제 홀수인 substring 과 짝수인 substring 으로 나뉠 수 있어서,
홀수인 경우에는 한 문자에서 양쪽으로 퍼져나가는 형식으로
짝수인 경우에는 두 문자에서 양쪽으로 퍼져나가는 형식으로 문자를 조합할 수 있다.

class Solutioin {
    public static boolean isPalindrom(String s){
     
     	int max = 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        
        int left = 0, right = 0;
        
        for(int i = n-1 ; i >= 0 ; i--){
        	for(int j = i ; j < n ; j++){
            	if((s.charAt(i) == s.charAt(j)) &&
                	(j - i < 2 || dp[i+1][j-1] )){
                    dp[i][j] = true;
                }
                
                if(j - i > max){
                    max = Math.max(max, j-i);
                    left = i;
                    right = j;
                }
           }
       }
       
       return s.substring(left, right+1);
	}
}

시간복잡도 O(n^2)가 걸리는 Dynamic Programming (DP) 쓰는 방법도 있다.
2차원 배열 dp[i][j] 는 i와 j 사이의 하위 문자열이 팔린드롬인지 여부를 나타낸다.
for 문 두개로 문자열을 순회하며 if문 조건이 두 개 걸리면 그 때 max 를 구하고 left, right 를 설정해준다.

따라서 고수했던 left, right 로 s의 substring 을 반환한다.

여기서 이해가 가지 않는 부분은 첫번째 if 문이다.
(j - i < 2 || dp[i+1][j-1]) 이 부분에서 왜 2여야 하며 i+1, j-1 이어야 하는지,,,, 모르겠다,,,