Loading...
墨滴

头顶金光的邪恶之星

2021/05/10  阅读:36  主题:雁栖湖

lt131- 分割回文串

figure1.png banner

131. 分割回文串

Difficulty: 中等

给你一个字符串 s,请你将s分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

题目分析

题意应该都清楚了,把一个字符串分割成若干回文串。希望你返回所有的分配方法。 然后呢,让我们一点点拨茧抽丝一下这个问题:

  • 由于单个字符构成的字符串是回文串,所以这道题不存在无解的情况。
  • 如果字符串所有字符都是一样的,那么最后的可能情况应该为 。此时我去看了一眼数据范围,字符串长度最长为16,时间复杂度可以承受。
  • 该问题是具有递归性质的,s的所有回文分割可以由s所有后缀的回文分割得到。看下面这张图,代表了aabb的回文分割。 figure1
  • 每条边代表删除的回文前缀。最后的分割方案,就是从aaba到空字符串的所有路径。从这张图中,我们可以看出,这个问题不仅可以通过递归解决,还具有公共子问题的特性,因此必然也能使用带记忆的搜索。

问题分析完毕,下面是代码,然而我是一条咸鱼,既然直接搜索能过这道题,就不写记忆化了。

Solution

Language: c++

class Solution {
public:
// 功能函数,判断一个字符串是否为回文
bool isPalindrome(string s){
    for (int i = 0, j  = s.length()-1; i < j; i++, j--){
        if (s[i] != s[j])
            return false;
    }
    return true;
}
vector<vector<string>>dfs(string s){
    // 如果字符串为空,返回唯一的分配方案,
    // 即一个空集
    if (s == ""return {{}};

    vector<vector<string>> ret;
    // 依次遍历前缀
    for (int i = 1; i <= s.length(); i++){
        string subs = s.substr(0, i);
        // 如果该子串为回文
        if (isPalindrome(subs)){
            // 获取剩余部分的字串分割方案
            auto parts = dfs(s.substr(i));
            // 把剩余部分的字串分配方案,
            // 加上当前字串,并合并答案
            for (auto& p: parts){
                p.push_back(subs);
                ret.push_back(p);
            }
        }
    }
    return ret;
}
vector<vector<string>> partition(string s) {
    vector<vector<string>> ret = dfs(s);
    // 写法问题,有由于我的写法类似于后序遍历,因此需要将所有答案反过来        
    for (auto& p: ret)
        reverse(p.begin(), p.end());
    return ret;
}
};

头顶金光的邪恶之星

2021/05/10  阅读:36  主题:雁栖湖

作者介绍

头顶金光的邪恶之星

华东师范大学 在读研究生