问题描述

• 对任意一个字符串进行切割，使得切割后的每一个字符串都是回文字符串。列出切割后的所有结果。

方法一：深度优先搜索

• 以string s的下标调用dfs函数，index表示当前要开始切割的下标，i表示目前要切割的终点位置，其中index<=i

//判断是否是回文
bool isPalindrome(string &s)
{
    for(int i=0;i2;i++)
    {
        if(s[i]!=s[s.length()-i-1])
            return false;
    }
    return true;
}

//字符串切割
//ans存放切割的所有结果
//cur存放当前的切割结果
void dfs(string &s,vector<<span class="hljs-stl_container" style="box-sizing: border-box;">vector<<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">string>>&ans,vector<<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">string> &cur,int index)
{
    if(index==s.length())
        ans.push_back(cur);
    else
    {
        for(int i=index;iif(isPalindrome(s.substr(index,i-index+1)))
            {
                cur.push_back(s.substr(index,i-index+1));
                dfs(s,ans,cur,i+1);
                cur.pop_back();
            }
        }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31

• 问题 
  
  • 上述代码很有可能会超时，因为每一个子串都要重新判断是否为回文串。
• 改进 
  
  • 声明一个变量表示从下标i开始j结束的字符串是否是回文vector>isPalind(s.length(),vector(s.length(),false));
  • 如果长度为len－2，下标开始地址为i+1的子串是回文串，并且s[i]==s[i+len-1],则说明长度为len,下标开始地址为i的子串也是回文串。即满足递归式isPalind[i][i+len-1]=isPalind[i+1][i+len-2]&&(s[i]==s[i+len-1])
  • 改进后的代码如下：

void isPalindrome(vector<<span class="hljs-stl_container" style="box-sizing: border-box;">vector<<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool>>&isPalind,string &s)
{
    for(int i=0;itrue;
    for(int i=1;i1]=true;
    for(int len=2;len<=s.length();len++)
    {
        for(int i=0;i+len<=s.length();i++)
        {
            isPalind[i][i+len-1]=isPalind[i+1][i+len-2]&&(s[i]==s[i+len-1]);
        }
    }
}

void dfs(string &s,vector<<span class="hljs-stl_container" style="box-sizing: border-box;">vector<<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">string>>&ans,vector<<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">string> &cur,int index,vector<<span class="hljs-stl_container" style="box-sizing: border-box;">vector<<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool>>&isPalind)
{
    if(index==s.length())
        ans.push_back(cur);
    else
    {
        for(int i=index;iif(isPalind[index][i])
            {
                cur.push_back(s.substr(index,i-index+1));
                dfs(s,ans,cur,i+1,isPalind);
                cur.pop_back();
            }
        }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32

在调用dfs函数之前，一定要先调用isPalindrome函数，生成isPalind数组。这样避免重复求一个字符是否是回文