leetcode hard : Maximum Number of Non-overlapping Palindrome Substrings

https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/

 

하아아아아아아아아앙아

너무 어려워

결국 답을 봐버렸고..

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        
        def isPal(i, j):                                        
            if j > len(s) : return False                      
            return s[i:j] == s[i:j][::-1]                     
        
        @lru_cache(None)                                      
        def dfs(i):                                           
            if i + k > len(s) : return 0                        
            result = dfs(i+1) # i+1부터 palindrome을 묶기 시작할 경우   
            if isPal(i,i+k)   : result = max(result, 1 + dfs(i+k))        
            if isPal(i,i+k+1) : result = max(result, 1 + dfs(i+k+1))      
            return result                 
        

        return dfs(0)

dfs(i)는 str[i:]에서의 문제 조건에 맞는 palindrome 최대 개수인듯하다

dfs(i)를 계산하기 위해 먼저 dfs(i+1)을 계산한다. 이건 str[i]가 palindrome에 포함되지 않는 경우를 가정하는거같다.

isPal(i, i+k) 이런식으로 i부터 시작하는 길이 k 혹은 k+1 (길이 홀짝인경우를 신경쓴듯) palindrome 검사를 하고 dfs(i+k) 이렇게 k만큼 스킵해서 묶은거랑 1을 더해서 palindrome 개수를 계산한다.

A......... 이거 시간복잡도 분석을 어떻게 하지? O(nk)라는디..

 

 

이 솔루션도 괜찮은듯

class Solution {
    public int maxPalindromes(String s, int k) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                int len = (j - i) + 1;
                if (len > k + 1) break; // this is the key 
                if (len >= k && isPalindrome(s, i, j)) {
                    ans++; i = j;  break;
                }
            }
        }
        return ans;
    }

    boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--))  return false;
        }
        return true;
    }
}

위 솔루션을 그리디 솔루션이고 파이썬으로 옮기면

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        
        def isPal(i, j):
            if j > len(s) : return False
            j -= 1
            while i < j:
                if s[i] != s[j]: return False
                i, j = i+1, j-1
            return True
        
        answer = 0
        
        i = 0
        while i < len(s):
            if isPal(i, i+k):
                answer += 1
                i = i + k
                continue
            if isPal(i, i+k+1):
                answer += 1
                i = i + k + 1
                continue
            i += 1
        return answer