131. Palindrome Partitioning

1.問題

• 給予一個字串, 分割為各種可能是回文的substring

2.想法

• 提問

• function header, parameter

• test input

• 觀察

  • 其實可以看成排列組合, 上一回起始點為0, 終點為n, 下一回合的起始點n + 1, 終點為m, 當m + 1為string.length時return

  • substr的用法

• 說明想法

• 測試計算複雜度

3.程式碼

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res; 
        vector<string> record;
        getSubStr(res, record, s, 0);
        return res;
    }
private:
    void getSubStr(vector<vector<string>>& res, vector<string>& record, string s, int start) {
        if (start == s.size()) {
            res.push_back(record);
            return; 
        }
        
        for (int i = start; i < s.size(); i++) {
            //substr的長度參數要算入自己
            int len = i - start + 1;
            string tmp = s.substr(start, len); 
            if (isPalindrome(tmp)) {
                record.push_back(tmp);
                getSubStr(res, record, s, i + 1); 
                record.pop_back();
            }
        }
    }
    
    bool isPalindrome(string s) {
        int size = s.length();
        for (int i = 0; i < size / 2; i++) {
            if (s[i] != s[size - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};