Wednesday, October 16, 2019

palindrome

palindrome

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];
        }
    }
}

No comments:

Post a Comment