c++ - Palindrome Partitioning(如何弄清楚如何使用DFS)

Question

我的一般问题是如何弄清楚如何使用 DFS。这似乎是我知识的薄弱部分。我的想法很模糊，但当问题发生变化时，我经常会卡住。这让我很困惑。

对于这个问题，我卡在了如何用递归编写 DFS 上。给定一个字符串 s , 分区 s这样分区的每个子串都是回文。

返回s所有可能的回文划分.

例如，给定s = "aab" ,

返回

  [
    ["aa","b"],
    ["a","a","b"]
  ]

我的第一次尝试卡在了辅助函数的循环中。然后通过互联网搜索，我发现 bool palindrome(string s)可以写成不同的签名。

bool palindrome(string &s, int start, int end)

这导致了正确的解决方案。

这是我最初尝试的代码:

class Solution {
public:
    bool palindrome(string s)  
    {
        int len = s.size();
        for (int i=0;i<len/2; i++)
        {
            if (s[i]!=s[len-i])
              return false;
        }
        return true;
    }

    void helper( int i, string s, vector<string> &p, vector<vector<string>> &ret)
    {
        int slen = s.size();
        if (i==slen-1&&flag)
        {
            ret.push_back(p);
        }


        for (int k=i; k<slen; k++)
        {
           if (palindrome(s.substr(0,k)))
           {
               p.push_back(s.substr(0,k));       //Got stuck
           }
        }
        i++;
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        int len=s.size();
        if (len==0) return ret;

        vector<string> p;
        helper(0,s,p,ret);
        return ret;
    }
};

正确的一个:

    class Solution {
    public:
        bool palindrome(string &s, int start, int end)
        {
            while(start<end)
            {
                if (s[start]!=s[end])
                   return false;
                start++;
                end--;
            }
            return true;
        }

        void helper( int start, string &s, vector<string> &p, vector<vector<string>> &ret)
        {
            int slen = s.size();
            if (start==slen)
            {
                ret.push_back(p);
                return;
            }

            for (int i=start; i<s.size(); i++)
            {
                if (palindrome(s, start, i))
                   {
                       p.push_back(s.substr(start,i-start+1));
                       helper(i+1,s,p,ret);
                       p.pop_back();
                   }
            }
        }

        vector<vector<string>> partition(string s) {
            vector<vector<string>> ret;
            int len=s.size();
            if (len==0) return ret;

            vector<string> p;
            helper(0,s,p,ret);
            return ret;
        }
    };

2014 年 12 月 4 日编辑:我看到了一些使用动态规划的方法，但无法完全理解代码。

尤其是isPalin[i][j] = (s[i] == s[j]) && ((j - i < 2) || isPalin[i+1][j-1]);

为什么 j-I<2而不是 j-I<1 ？

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int len = s.size();
        vector<vector<string>> subPalins[len+1];

        subPalins[0] = vector<vector<string>>();
        subPalins[0].push_back(vector<string>());

        bool isPalin[len][len];

        for (int i=len-1; i>=0; i--)
        {
            for (int j=i; j<len; j++)
            {
                isPalin[i][j] = (s[i]==s[j])&&((j-i<2)||isPalin[i+1][j-1]);
            }
        }

        for (int i=1; i<=len;i++)
        {
            subPalins[i]=vector<vector<string>>();

            for (int j=0; j<i; j++)
            {
                string rightStr=s.substr(j,i-j);

                if (isPalin[j][i-1])
                {
                    vector<vector<string>> prepar=subPalins[j];

                    for (int t=0; t<prepar.size(); t++)
                    {
                        prepar[t].push_back(rightStr);
                        subPalins[i].push_back(prepar[t]);
                    }
                }
            }
        }

        return subPalins[len];
    }
};

Answer 1

你到底在问什么？您有正确的工作代码和没有太大区别的非工作代码。

我想我可以指出您的代码的几个问题 - 可能对您有所帮助:

1. 在 palindrome() 中您应该比较的功能 s[i]至 s[len-1-i]而不仅仅是 s[len-i]在if ，因为在前一种情况下，您会将第一个元素(索引为 0)与不存在的元素(索引 len)进行比较。这可能就是原因 helper()卡住了。

2. 在 helper() 中函数 flag未初始化。在for循环，结束条件应该是k<slen-1而不是 k<slen ，因为在后一种情况下，您将忽略检查包含字符串终端符号的子字符串。此外，递增 i在helper()结束毫无意义。最后，helper() 中的缩进很乱。功能。

不确定为什么要使用 DFS - 你的图是什么意思，这里的顶点和边是什么？至于这里的递归如何工作:在 helper() 中函数开始检查长度增加的子串是否为回文。如果找到回文，则将其放入 p vector (代表您当前的分区)并尝试通过调用 helper() 将字符串的其余部分分解为回文递归地。如果你成功了(即，如果整个字符串被完全划分为回文)，你将放置 p 的内容。 vector (当前分区)到 ret (所有找到的分区的集合)，然后清除 p为下一个分区的分析做准备(清除 p 是通过 pop_back() 调用在 helper() 的递归调用之后实现的)。另一方面，如果您无法将字符串完全分解为回文，则 p也被清除，但没有将其内容转移到 ret (这是因为对最后一段字符串的递归调用 - 这不是回文 - 返回时没有为最终符号调用 helper()，因此不会将 p 插入 ret )。因此，您最终在 ret 中拥有所有可能的回文分区。 .