- 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 셋팅
- left +1 <= right-1 ( size가 3이상인 경우)
사이즈가 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