LeetCode #131：Palindrome Partitioning(分割回文串)

题目描述

本题的核心逻辑是：依次截取串 s 的若干子串 s[0...i]，其中 i 的范围为 [0, length(s) - 1]。若子串 s[0...i] 是回文串，将其加入待定答案序列 temp 中，将 s 替换为 s[i+1...] 往下一层递归执行；若 s[0...i] 不是回文串，则 i++，看 s[0...i+1] 是否是回文串。直到没有字符可划分时，划分完毕，将 temp 加入最终答案。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        dfs(s);

        return res;
    }

    vector<vector<string>> res;
    vector<string> temp;
 
    void dfs(string s) {
        if(s.length() == 0) { // 划分完毕
            res.push_back(temp);
            return;
        }
            
        for(int i = 1; i <= s.length(); i ++) {
            string str = s.substr(0, i);
            if(isPalindrome(str)) { // 若子串s[0...i]是回文串，将其加入待定答案序列temp中
                temp.push_back(str);
            } else {
                continue;
            }
            dfs(s.substr(i)); // 将s替换为s[i+1...]继续执行，这里参数写i是因为substr的性质
            temp.pop_back();
        }
    }

    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;
    }
};