LeetCode 131解法中list = new List<string>(list)的作用是什么？

解法代码 #

public class Solution 
{
    public IList<IList<string>> Partition(string s) 
    {
        IList<IList<string>> res = new List<IList<string>>();
        CheckSubstring(new List<string>(), s, res, 0);
        return res;
    }

    void CheckSubstring(List<string> list, string s, IList<IList<string>> res, int startIndex)
    {
        if (startIndex == s.Length)
        {
            list = new List<string>(list);
            res.Add(list);
            return;
        }
        for (int end = startIndex; end < s.Length; end++)
        {
            string sub = s.Substring(startIndex, end - startIndex + 1);
            if (IsPalindrome(sub))
            {
                list.Add(sub);
                CheckSubstring(list, s, res, end + 1);
                list.RemoveAt(list.Count - 1);
            }
        }
    }

    bool IsPalindrome(string s)
    {
        int left = 0, right = s.Length - 1;
        while (left < right)
        {
            if (s[left] != s[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

问题解答 #

你说的没错，这行代码确实是创建原列表的副本，这么做的核心原因是回溯过程中我们复用了同一个list对象：

在整个递归回溯流程里，我们会不断给list添加回文子串，递归结束后又会删除最后添加的元素（也就是list.RemoveAt(list.Count - 1)这步），以此尝试不同的分割组合。如果直接把原list加到res里，res中保存的其实是这个list对象的引用——后续的删除操作会直接修改res里已经存进去的列表内容，最后所有结果都会变成空或者错误状态。

而通过new List<string>(list)创建副本后，我们把这个独立的新列表加到res里，它的内容就固定下来了，不会再被后续回溯操作修改，这样res里才能保存正确的分割结果。

内容的提问来源于stack exchange，提问作者Liu_064