A C# Time O(N2) Space O(n) Solution

• Time O(n2) Space O(n2)

``````public int MinCut(string s){
byte[,] dp = new byte[s.Length, s.Length];
for (int i = s.Length - 1; i >= 0; i--)
for (int j = i; j < s.Length; j++)
if (s[i] == s[j] && (j - i <= 2 || dp[i + 1, j - 1] == 1))
dp[i, j] = 1;
int[] result = new int[s.Length];
for (int i = 0; i < result.Length; i++) result[i] = result.Length;
for (int j = 0; j < s.Length; j++)
for (int i = 0; i <= j; i++)
if (dp[i, j] == 1)
result[j] = Math.Min(result[j], i == 0 ? 0 : result[i - 1] + 1);
return result[s.Length - 1];
}
``````

Space O(n) Time O(n2)

``````public int MinCut(string s) {
if(s.Length < 2) return 0;
int[] dp = new int[s.Length];
for(int i = 0; i < dp.Length; i++) dp[i] = i;
for(int i = 0; i < dp.Length; i++){
for(int j = 0; i - j >= 0 && i + j < s.Length && s[i - j] == s[i + j]; j++)
dp[i + j] = i - j == 0 ? 0 : Math.Min(dp[i - j - 1] + 1, dp[i + j]);
for(int j = 1; i - j + 1 >= 0 && i + j < s.Length && s[i - j + 1] == s[i + j]; j++)
dp[i + j] = i - j + 1 == 0 ? 0 : Math.Min(dp[i - j] + 1, dp[i + j]);
}
return dp[s.Length - 1];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.