<Hard> Palindrome Partitioning II (LeetCode : C#)

https://leetcode.com/problems/palindrome-partitioning-ii/

📕 문제 설명

주어진 문자열의 하위 문자열이 palindrome이 되도록 하는 자르는 횟수

• Input
  문자열
• Output
  자르는 횟수 (int)

예제

풀이

public class Solution {
    public int MinCut(string s) {
       var n = s.Length;
        var isPalindromes = new bool[n, n];

        // len = 1 일때는 true로 초기화
        for (int i = 0; i < n; i++) {
            isPalindromes[i, i] = true;
        }
        // 각 index 별 palindrome check
        for (int right = 1; right < n; right++) {
            for (int left = 0; left < right; left++) {
                if (s[left] == s[right] && (left + 1 == right || isPalindromes[left + 1, right - 1])) {
                    isPalindromes[left, right] = true;
                }
            }
        }

        int[] cuts = new int[n];
        for(int i=0; i<n; i++)
        {
            int temp = Int32.MaxValue;
            if(isPalindromes[0, i]) cuts[i] = 0; // 첫 단어 ~ 현재 index 까지 palindrome이면 cut = 0
            else
            {
                for(int j = 0; j < i; j++) // 앞에서부터 하나씩 끊어보면서 제일 cut 작은걸로 update
                {
                    // 앞은 확인 안해도 되는게 cuts[j] + 1 확인하므로 이미 앞이 확인되었다 볼 수 있음 (ex - bana 에서)
                    // (b, ana) (ba, na) (ban, a) 보게 되는데 2번째 케이스의 경우 j가 2번째 index 가리키고 이건 이미 앞의 cut 포함해서 값 가지고 있음
                    if((isPalindromes[j + 1, i]) && temp > cuts[j] + 1) // cut한 후 오른쪽이 palindrome이면서 최소면 갱신 
                    {
                        temp = cuts[j] + 1;
                    }
                }
                cuts[i] = temp;
            }			  
        }
        return cuts[n-1];
    }
}

결과