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


  • 0
    L

    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];
    }

Log in to reply
 

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