Wednesday, February 5, 2014

Palindrome Partitioning I -- Leetcode

class Solution {
public:
    vector<vector<string>> partition(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
     vector<vector<string>> res,subres;
     vector<string> vs;
   
     if(s.length()==0){
         return res;
     }
     if(s.length()==1){
         vs.push_back(s);
         res.push_back(vs);
         return res;
     }

     for(int i=1;i<=s.length();++i){          
        if(ispalindrome(s.substr(0,i))){
            subres=partition(s.substr(i,s.length()-i));
         
            if(subres.size()==0){
                vs.push_back(s.substr(0,i));
                res.push_back(vs);
            }
            else{
                for (int j=0;j<subres.size();++j){
                     subres[j].insert(subres[j].begin(),s.substr(0,i));
                     res.push_back(subres[j]);
                }
            }            
        }          
    }
     return res;    
    }
 
    bool ispalindrome(string s){
       for(int i=0;i<s.length();++i){
        if(i<=s.length()/2){
          if(s[i]!=s[s.length()-i-1])
          return false;
        }
        else break;
       }
       return true;
    }
};

No comments:

Post a Comment