leetcode 5. Longest Palindromic Substring c++

문제

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

예시

• Input = "babad" / output = "bab"
• Input = "aca" / output = "a"
• Input = "cbbd" / output = "bb"

 

string과 DP가 복합적으로 들어간 펠린드롬 문제이다.

 

풀면서 자꾸 막혔던 부분은, 모든 범위의 펠린드롬을다 확인해야했다는 것이다.

백준에서 풀었던 펠린드롬은 범위가 주어졌었지만, 이번엔 안주어졌기 때문이다.

 

그래서 이중 for문으로 모두 확인하도록 했다.

 

왼쪽=i , 오른쪽은=j 라고 할때,

왼쪽 끝은 고정하고 오른쪽 맨끝부터 하나씩 줄여가면서 확인하는 방식이다.

그리고 왼쪽 끝과 오른쪽 끝이 만나면, 왼쪽을 +1 한 뒤 다시 오른쪽 끝부터 확인한다.

 

만약 펠린드롬을 찾았다면 그 i 루프는 더 이상 돌 필요 없다.

그 i 루프에서 가장 긴 펠린드롬을 찾은 것이기 때문이다.

 

추가적으로 펠린드롬을 찾았을때, 가장 긴 문자의 길이를 계속 유지만 해주면 된다.

 

아래는 내 코드이다.

 

int d[1000][1000];
string str;

class Solution {
public:
    string longestPalindrome(string s) {
        for(int i=0; i<s.size(); i++)
            for(int j=0; j<s.size(); j++)
                d[i][j]=-1;
        
        int x=0; int y=0;
        str = s;
        
        for(int i=0; i<s.size()-1; i++){
            for(int j=s.size()-1; j>i; j--){
                if(d[i][j] != -1) break;
                if(dfs(i,j)){
                    if(y-x < j-i){
                        x=i; y=j;
                    }
                    break;
                }
            }
        }
        
 
        return s.substr(x,y-x+1);
    }
    
    bool dfs(int x, int y){
        if(d[x][y] != -1) return true;
        
        if(x==y){
            d[x][y]=1;
            return true;
        }
        
        if(y-x == 1){
            if(str[x] == str[y]){
                d[x][y]=1; return true;
            }
            else{
                d[x][y]=-1; return false;  
            } 
        }
        
        if(str[x] == str[y] && dfs(x+1, y-1)){
            d[x][y] = 1; return true;
        }
        else{
            d[x][y] = -1; return false;
        }
    }
    
};