[力扣] 算法 131 (C#)

131. 分割回文串

public class Solution
{
    public IList<IList<string>> Partition(string s)
    {
        if (s.Length == 0)
            return new List<IList<string>>();
        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];
        var ret = new List<IList<string>>();
        var temp = new List<string>(s.Length);
        Foo(ret, temp, 0, part, s);
        return ret;
    }

    void Foo(List<IList<string>> ret, IList<string> temp, int index, bool[,] part, string s)
    {
        if (index == s.Length)
        {
            ret.Add(new List<string>(temp));
        }
        else
        {
            for (var i = index; i < s.Length; i++)
            {
                if (!part[index, i])
                    continue;
                temp.Add(s[index..(i + 1)]);
                Foo(ret, temp, i + 1, part, s);
                temp.RemoveAt(temp.Count - 1);
            }
        }
    }
}

发表评论