[LeetCode 647] Palindromic Substrings with JAVA (BruteForce)

leetcode.com/problems/palindromic-substrings/

Palindromic Substrings - LeetCode

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

 

Example 1:

Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

 

Example 2:

Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

class Solution {
    public int countSubstrings(String s) {
        int size = s.length();
        int ans = 0;

        for (int i = 0; i < size; i++){
            for (int j = i+1; j <= size; j++){
                if (isPalid(s.substring(i, j))){
                    ans++;
                }
            }
        }
        return ans;
    }
    public boolean isPalid(String s){
        int size = s.length();
        for (int i = 0; i < size / 2; i++){
            if (s.charAt(i) != s.charAt(size-i-1)){
                return false;
            }
        }
        return true;
    }
}

1. 어려웠던 점:

없다.

 

2. 알게된 점:

팰린드롬 복습

 

3. 알고리즘 풀이:

처음엔 투 포인터를 생각했으나, 완전 탐색을 해야 할 것 같아 이중 for문과 다를 게 없어 이중 for문으로 구현하였다.

완전탐색을 하지 않고 하는 방법이 있는지는 검색해보아야겠다.

 

0..n의 char 배열이 되는 문자열이라면, 0부터 시작하는 substring을 모두 판별

1부터, 2부터 .. n부터 까지 판별하면 된다.

 

팰린드롬 판별은 

waristo.tistory.com/4?category=977039

[백준 1747] 소수&팰린드롬 with JAVA

에서 설명했듯이, 중간을 기준으로 왼쪽을 기준으로만 판별하면 되기 때문에 (두 번 비교하지 않기 위해)

for문을 2/size까지만 돌리면 된다.

홀수일 경우, 마지막 중앙값은 팰린드롬 여부와 아무런 상관이 없기 때문에 홀수, 짝수 구분도 필요하지 않다.

 

 

-2021.04.15 수정

알고리즘 스터디로 브루트포스가 아닌 다이나믹 프로그래밍으로 기존 값을 저장할 수 있음을 알게되었다.

당연히 다이나믹 프로그래밍의 시간복잡도가 더 낮을 것이다.

다음에 다이나믹 프로그래밍 버전의 코드를 다시 올리겠다.