[LeetCode- Part. 2] 4. 가장 긴 회문 부분 문자열 (+ 2차원 DP) #

https://leetcode.com/problems/longest-palindromic-substring/submissions/

Longest Palindromic Substring - LeetCode

 

 

---

(1) 이중 for문 이용 : 타임 리밋 발생

class Solution {
    public String longestPalindrome(String s) {
        int cnt=Integer.MIN_VALUE;
        String answer="";
        //문자열에서 가장 긴 회문 부분 문자열 리턴
        //boolean[] dp = new boolean[s.length()+1];
        for(int i=0;i<s.length();i++){
            char[] arr= s.toCharArray();
            StringBuilder sb = new StringBuilder();
            for(int j=i; j<s.length();j++){
                sb.append(arr[j]);
                System.out.println(sb.toString()+" "+sb.reverse().toString());

                if((sb.toString()).equals((sb.reverse()).toString())){
                    //System.out.println(sb.toString()+" "+sb.reverse().toString());
                    cnt=Math.max(cnt,sb.toString().length());
                    if(sb.length()==cnt) answer=sb.toString();
                }
            }
        }       
        
        return answer;
    }
}

 

2. DP 이용

: 2차원 DP를 이용해 -> 2가지를 비교해 가면서 메모이제이션을 진행한다.

 

 

문제 해결 순서

1. Palindrome 특징
앞으로 보나, 뒤로 보나 글자가 같아야 한다.

 

2. 맨끝 문자 a가 같아야 한다.

s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])

 

2-1. s.charAt(i) == s.charAt(j)

문자 a가 같아야 한다.

 

2-2. (i - j < 2 || dp[j + 1][i - 1])

b, a, n, a 각각의 글자는 palindrome ==1 이다
j=1 i=3일때 dp[2][2]== true를 이용해 (DP 재사용성)

중심 글자 양옆이 같아야 함 -> 중간 문자가 같다.

 

 

 

 

class Solution {
    public String longestPalindrome(String s) {
        //1.ds
        int n=s.length();
        boolean[][] dp = new boolean[n][n];
        String result="";
        
        //2.loop
        for(int i=0; i<n;i++){
            for(int j=i; j>=0; j--){
                //System.out.println("dp["+j+"]["+i+"]"+dp[j][i]);
                //조건 설정
                //(1) 문자열 시작과 끝이 같다.
                //(2) 문자열 인덱스의 차이가 2보다 작거나, 중간 문자가 같다. -> 중간 문자 dp가 true다
                
                if(s.charAt(i)==s.charAt(j) &&(i-j<2 || dp[j+1][i-1])) {
                    dp[j][i]=true;
                    
                    //결괏값이 초기값이거나, 이전의 결괏값의 길이보다 현재 구한 길이가 길 때
                    if(result.equals("")||i-j+1>result.length()){
                        result=s.substring(j, i+1);
                    }
                }
            }
            //System.out.println("");
            
        }
        
        return result;
    }
}

 

 

class Solution {
    public String longestPalindrome(String s) {
        String result = null;
        int n=s.length();
        boolean[][] dp = new boolean[n][n];
        
        for(int i=0;i<n;i++){
            for(int j=i;j>=0;j--){
                
                if(s.charAt(i)==s.charAt(j) &&(i-j<2||dp[j+1][i-1])){
                    //0,0
                    //0,1
                    //0,2
                    dp[j][i]=true;
                    //System.out.println("dp["+j+"]["+i+"]"+dp[j][i]);
                    
                    if(result==null || i-j+1>result.length()){
                        result=s.substring(j, i+1);
                    }
                }
            }
        }
        return result;
    }
}