[LeetCode] Palindrome Partitioning

Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s =  "aab" , Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

問題解決の考え方:
問題は、文字列に対するすべての区分を探し出し、各区分が回文であるようにすることを意味する.再帰的な方法で作る.
注意s.substr(i);メソッドは、iがsの長さに等しい場合、空の文字列を返します.iがsより大きい場合は、エラーを報告します.

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        
        vector<string> item;
        
        helper(item, s, result);
        
        return result;
    }
    
    void helper(vector<string>& item, string s, vector<vector<string>>& result){
        int len = s.length();
        if(len == 0 && item.size()>0){
            result.push_back(item);
            return;
        }
        for(int i=0; i<len; i++){
            string s1 = s.substr(0, i + 1);
            if(isPalindrome(s1)){
                item.push_back(s1);
                helper(item, s.substr(i + 1), result);
                item.pop_back();
            }
        }
    }
    
    bool isPalindrome(string& s){
        int len = s.length();
        int i=0, j=len-1;
        while(i<j){
            if(s[i]!=s[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};