palindrome

• DP가 약하기도하고 공부도 하고 내용도 복습할겸 정리합니다.
• 기본에서 true 와 false말고 숫자로 표현하면 응용이 가능하다.
• 참고 링크 https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

dp 문제를 푸는 나름대로의 방법

• DP 에서 row와 column에 어떤값을 정확하게 넣어야 할지가 분명하게 서지 않을때 그림을 그리는것은 도움이 된다.

문제

• 여러개의 특정 포지션에서 해당 substring이 palindrome인지 체크 하는 로직을 만드세요
• left = 시작 지점 right = 끝 지점
• ex) str = “abad”

풀이

• T = true, F = false로 간주한다.
• table[left][right]에 대한 값을 담을 수 있는 table을 만들고 값을 채워나간다.
• left == right 같을때는 T 로 셋팅
• left != right
  • left +1 <= right-1 ( size가 3이상인 경우)
    • str[left] == str[right] && table[left+1][right-1] 인경우 table[left][right] T 셋팅
  • left +1 > right-1 ( size 가 2인경우 )
    • str[left] == str[right] 인 경우 table[left][right] T 셋팅

사이즈가 1인경우

사이즈가 2이고 left = 0, right =1 인경우

사이즈가 3이고 left = 0 right =2 인경우

코드

String s = "abac";
boolean[][] table = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
    table[i][i] = true;
}
for(int size=2; size<s.length(); size++){
    for(int left=0; left<s.length(); left++){
        int right= left+size-1;
        if(right >= s.length()){
            continue;
        }
        if( size == 2){
            table[left][right] = s.charAt(left) == s.charAt(right);
        }else{
            table[left][right] = s.charAt(left) == s.charAt(right) && table[left+1][right-1];
        }
    }
}