.leetcode(647. Palindromic Substrings)

문제

https://leetcode.com/problems/palindromic-substrings/

문제 풀기 전

1. subset 어떻게 풀었더라
2. checkPalindromic 시작점, 끝점 메소드를 이용하면 좀 더 빨라지겠다.

직접 푼 풀이

소요시간: 15분(18:19 ~ 18;34)

#Brute force
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int k=1; k<n+1; k++) {
            for (int i=0; i<n+1-k; i++) {
                String sub = s.substring(i,i+k);
                if(checkPalindromic(sub)) {
                    count++;
                }
            }
        }

        return count;
    }

    private boolean checkPalindromic(String s) {
        for(int i=0, j=s.length()-1; i<s.length()/2;) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }

        return true;
    }
}

# dp
class Solution {
    private String fullString;
    private int[][] cache;
    public int countSubstrings(String s) {
        fullString = s;
        int n = s.length();
        cache = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                cache[i][j] = -1;
            }
        }
        int count = 0;
        for (int k=1; k<n+1; k++) {
            for (int i=0; i<n+1-k; i++) {
                if(checkPalindromic(i, i+k-1) == 1) {
                    count++;
                }
            }
        }

        return count;
    }

    private int checkPalindromic(int start, int end) {
        if (cache[start][end] != -1) {
            return cache[start][end];
        }

        if (start >= end) {
            return 1;
        }

        int ret = 0;
        if (fullString.charAt(start) == fullString.charAt(end)) {
           if (checkPalindromic(start+1, end-1) == 1) {
               ret = 1;
           }
        }

        return cache[start][end] = ret;
    }
}

느낀점

1. 반복이 된다 싶을때는 count를 구하는 문제면 dp로 문제를 풀어보는것도 좋은 습관이다. 다만 반복되는 점이 보여도 모든 경우의 수 출력과 같은 경우는 다르다.
2. 우리가 이미 큰 palindromic을 구하면 자기보다 크기가 작고 중심이 같으면 이미 panlindromic을 어떻게 구하지 했는데 솔루션3번에서는 그걸 구현했다. 이건 이해하고 다음에 다시 풀어보도록 한다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int countSubstrings(String s) {
        int count = 0;

        for (int i=0; i<s.length(); i++) {
            count += countFromMiddle(s, i, i);
            count += countFromMiddle(s, i, i+1);
        }

        return count;
    }

    private int countFromMiddle(String s, int lo, int hi) {
        int count = 0;
        while(lo>=0 && hi<s.length()) {
            if(s.charAt(lo) != s.charAt(hi)) {
                break;
            }

            lo--;
            hi++;
            count++;
        }

        return count;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• palindromic 양파버젼으로 풀어보기