릿코드 - Longest Palindromic Substring (팰린드롬)

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

 

Example 1:

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

Example 2:

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

 

주어진 문자열에서 가장 긴 팰린드롬 문자열을 구하는 문자

 

팰린드롬이란?

aba, aabbaa 처럼 뒤집어도 똑같은 문자가 나오는 문자열

 

풀이방법

1) 2중 for문으로 가능한 모든 문자열의 경우의 수 출력

2) 해당 문자열이 팰린드롬인지 확인

  -> DP의 개념이 사용된다.

3) 팰린드롬 문자열 중에 최댓값 저장

 

처음에는 문자열 팰린드롬 확인할 때 String의 reverse함수 사용해서 비교했는데 이렇게 하니까 시간초과가 떳다.

인터넷 검색을 참고해서... 새로 만들었다.

 

* 팰린드롬 문자열 확인하는 법(cal함수)

먼저 s(i)>=e(j) 이면 1을 리턴하고, 비교할 문자열의 시작점과 끝점의 알파벳이 같을 경우에 시작점+1, 끝점-1을 또 비교한다.

비교를 하면서 해당 부분 문자열들은 결과를 저장해두고, 한번 계산한 문자열은 다시 판단을 하지 않는다.

 

import java.util.*;

class Solution {
    int[][] dp;
    public String longestPalindrome(String s) {
        String max = "";
        dp = new int[s.length()][s.length()];
        
        if(s.length()==1) return s;
        
        for(int i=0; i<s.length(); i++){
            for(int j=i; j<s.length(); j++){
                    if(cal(i,j,s) > 0){
                        if(max.length() < j-i+1)
                            max = s.substring(i,j+1);
                    }
                } 
            }
        
        return max;
    }
    
    public int cal (int s, int e, String res){
        if(s>=e) return 1;
        
        if(dp[s][e] > 0){
            return dp[s][e];
        }
        
        int ret = -1;
        
        if(res.charAt(s) == res.charAt(e)){
            ret = cal(s+1,e-1,res);
        }
        
        dp[s][e] = ret;
  
        return ret;
    }
}