LeetCode 131 Palindrome Partitioning

概述

https://leetcode.com/problems/palindrome-partitioning/

暴力遍历法

显然：

1. 每个单字符都是一个合法的回文子串。
2. 每个更长的回文子串可以视为由较小的生长而来，偶数的回文子串是由两个连续的相同字符的子串生长而来。

好好读题目行不行，我们需要保证划分后的所有子串都是回文串。

回溯法

我们必须保证开头的是一个回文串，剩下的递归咯。

class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<string>> partition(string s) {
        vector<string> res;
        helper(s, 0, res);
        return ans;
    }
    
    bool isValid(string& s, int l, int r) {
        bool ok = true;
        while (l < r) {
            if (s[l] != s[r]) return false;
            l ++;
            r --;
        }
        return ok;
    }
    
    void helper(string& s, int k, vector<string>& res) {
        if (k == s.size()) {
            ans.push_back(res);
            return;
        }
        string t;
        for (int i = k; i < s.size(); i ++) {
            t += s[i];
            if (isValid(s, k, i)) {
                res.push_back(t);
                helper(s, i+1, res);
                res.pop_back();
            }
        }
    }
};

Links: leetcode-131-palindrome-partitioning

未经允许，禁止转载，本文源站链接：https://iamazing.cn/