Letcode에서 최대 메모 하위 문자열 찾기

1879 단어
동적 기획으로 하다.사고방식은 매우 간단하다.maintain은 하나의 dp의 2차원 그룹으로 그 안에 dp[i][j]의 상태를 기록한다.true는 바로 I에서 j까지의 하위 문자열이palindrome이다.베이스와 Recursive case를 나눈다. 베이스는substring의 길이가 1 또는 2이고 s[i]와 s[j]를 직접 비교하면 recursive: 만약에 s[i]가 s[j]와 같고 s[i+1][j-1]도palindrome이면 dp[i][j]를true로 설정합니다.동시에 maintain의 max 수조는 최대 길이의palindrome의 시작 index와 끝 index를 기록합니다.코드:
class Solution {
        public String longestPalindrome(String s) {
            if (s.length()<=1) return s;
            int length = s.length();
            boolean[][] dp = new boolean[length][length];
            int[] max = new int[2];
            for (int i = length; i > -1; i--){
                for (int j =i+1; j < length; j++){
                    // base case: 1 or 2
                    if (j - i <= 2){
                        if (s.charAt(i)==s.charAt(j)) {
                            dp[i][j]=true;
                            if (j-i+1 > max[1]-max[0]+1){
                                max[0]=i;
                                max[1]=j;
                            }
                        }
                    }
                    else {
                        if (s.charAt(i)==s.charAt(j) && dp[i+1][j-1]==true) {
                            dp[i][j]=true;
                            if (j-i+1 > max[1]-max[0]+1){
                                max[0]=i;
                                max[1]=j;
                            }
                        }
                    }
                }
            }
            return s.substring(max[0], max[1]+1);
        }
    }

어려운 점이 하나 있다. 바로 두루 훑어보는 순서 문제, 두 가지 중요한 점: 1.j는 i보다 커야 합니다. 2.i를 훑어볼 때 역방향으로 훑어보아야 한다.consider:'edcbabcdz'라는 예:'dcbabcd'는palindrome이지만 정방향으로 훑어보면'cbabc'라는 문자열의 상태는false이다. 아직 훑어보지 않았기 때문에 반대로'cbabc'는 이미true로 지정되어 있는데 왜 이렇게 느린지 궁금하다. 40ms, beat 41%, O(n^2)
개발판 Docker와 Docker Registry의 검증 환경을 만들어 보세요.
UVA 10163 Storage Keepers

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage