[Algorithm] LeetCode 647. Palindromic Substrings (java)

 

 

사고 과정

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

기본적인 palindrome 문제. 다만, 해당 String이 회문인지 아닌지 여부를 반환하는 것이 아닌, 

해당 문자열 내에서 회문이 될 수 있는 연속된 문자열의 조합 수를 반환해야 했던 문제!

 

Constraints에서 정해주길 String s 의 길이는 1 이상이고, 모두 소문자라고 하니, 나름 출제자의 배려(?)가 보였던 문제. 

 

접근 방법은 크게 dp와 dp가 아닌 방법이 있을 것 같다. 우선 dp가 아닌 방법 먼저 살펴보자.

 

Solution 1. Brute Force 

 

그냥 문자열을 하나의 문자열로 분해하고, n개의 연속된 문자끼리 조합했을 때, 회문이라면 count해주고, 회문이 아니라면 count 안해주는 방식이면 되지 않을까..? 에서 출발한 풀이법. 

 

class Solution {
    
    public boolean checkIsPalindrome(String s, int left, int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)) return false;
            left ++;
            right --;
        }
        
        return true;
    }
    
    public int countSubstrings(String s) {
        int count = 0;
        
        for(int l = 0; l < s.length(); ++l){
            for(int r = l; r < s.length(); ++r){
                count += (checkIsPalindrome(s, l, r)) ? 1 : 0;
            }
        }
        
        return count;
    }
}

 

그런데,, 시간 복잡도 측면에서 생각해보면 너무 비효율적인 코드다. 각각의 메서드로 나눠봤는데, 따로따로 시간복잡도를 생각해보면 

checkIsPalindrome 메서드의 time-complexity 는 O(N). 

countSubstrings 메서드의 time-complexity는 O(N^2). 

 

따라서 총 O(N^3)의 시간 복잡도를 갖게 된다! 

 

줄일 순 없을까..

 

Solution 2. Dynamic Programming