[力扣] 算法 132 (C#)

132. 分割回文串 II

public class Solution
{
    public int MinCut(string s)
    {
        if (s.Length == 0)
            return 0;
        var part = new bool[s.Length, s.Length];
        part[0, 0] = true;
        for (var i = 1; i < s.Length; i++)
            part[i, i] = part[i, i - 1] = true;
        for (var i = 1; i < s.Length; i++)
            for (var j = 0; j < s.Length - i; j++)
                part[j, i + j] = part[j + 1, i + j - 1] && s[j] == s[i + j];

        // 这一段原本我是用131的的Foo()改的,结果超时了。按官方的解法写了如下代码
        var f = new int[s.Length];
        Array.Fill(f, s.Length);
        for (var i = 0; i < s.Length; i++)
            if (part[0, i])
                f[i] = 0;
            else
                for (var j = 0; j < i; j++)
                    if (part[j + 1, i])
                        f[i] = Math.Min(f[i], f[j] + 1);
        return f[^1];
    }
}

发表评论