Palindrome Partitioning II - LeetCode

Problem

1. input: 문자열 s
2. output: s를 쪼개어, 모든 부분문자열이 팰린드롬이 되게 하려고 할 때, 필요한 최소한의 분할 횟수 리턴
   • 1 <= s.length <= 2000
   • s consists of lowercase English letters only.

Idea

이런 문제는 결국 모든 경우를 다 확인해봐야 한다. 하지만 완전탐색은 당연히 시간초과가 날 것이다.

전체를 부분으로 쪼개는 문제이기 때문에 하위 문제에서 중복되는 연산이 존재한다. DP(Memoization)으로 풀면 되는 문제이다. → Sol1

Solution

1. DP(Memoization)

   모든 분할 기준에 대해 분할하며, 최소 분할 횟수 갱신

   ⇒ memo를 통해 중복된 연산 X

   class Solution {
       val memo = hashMapOf<String, Int>()
       fun minCut(s: String): Int {
           val N = s.length
           return recDP(s, 0, N - 1)
       }
   		
       fun recDP(s: String, startIdx: Int, endIdx: Int): Int {
   				// 범위 밖이거나 이미 팰린드롬인 경우, 0 리턴
           if (startIdx >= endIdx || isPalindrome(s, startIdx, endIdx)) return 0
   				// memo한 값이 있는 경우, 저장한 값 리턴
           if (memo.contains("$startIdx $endIdx")) return memo["$startIdx $endIdx"]!!
           var min = endIdx - startIdx // 최소값은 모든 문자를 하나하나 분리한 횟수
           for (i in startIdx..endIdx) { // 모든 중간 기준(쪼개는)에 대해 탐색
               if (isPalindrome(s, startIdx, i)) {
                   min = minOf(min, recDP(s, i + 1, endIdx) + 1) // 최소 분할 횟수 갱신
               }
           }
           memo["$startIdx $endIdx"] = min
           return memo["$startIdx $endIdx"]!!
       }
   
   		// 주어진 문자열이 해당 범위에서 팰린드롬인지 확인
       fun isPalindrome(s: String, start: Int, end: Int): Boolean {
           var (i, j) = Pair(start, end)
           while (i < j) {
               if (s[i++] != s[j--]) return false
           }
           return true
       }
   }
   

   시간 복잡도: 문자열 탐색(분할) X 문자열 탐색(팰린드롬 확인) = n^2

   

Point