本文共 1905 字，大约阅读时间需要 6 分钟。

class Solution {public:	bool IsPalindrome(string str, int startIdx, int endIdx)	{		while (startIdx < endIdx)		{			if(str[startIdx] != str[endIdx])				return false;			startIdx++;			endIdx--;		}		return true;	}	void DFS(string& str, int startIdx, vector
   
    & curSubStrs, vector
    
     
      >& result)	{		if (startIdx == str.size())		{			result.push_back(curSubStrs);			return;		}		for (int i = startIdx; i < str.size(); ++i)		{			if ( IsPalindrome(str, startIdx, i) )			{				curSubStrs.push_back(str.substr(startIdx, i-startIdx+1));				DFS(str, i+1, curSubStrs, result);				curSubStrs.pop_back();			}		}	}	vector
      
       
        > partition(string s) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		vector
        
          curSubStrs; vector
         
          
           > result; DFS(s, 0, curSubStrs, result); return result; }};
          
         
        
       
      
     
    
   

second time

class Solution {public:    void partitionUtil(string& s, vector
   
    
      >& isP, int curIdx, vector
     
      & curPath, vector
      
       
         >& allPath)    {        if(curIdx == s.size())        {            vector
        
          curStr; // int end = s.size(); for(int i = curPath.size()-1; i >= 0; --i) { curStr.push_back(s.substr(curPath[i], end-curPath[i])); end = curPath[i]; } reverse(curStr.begin(), curStr.end()); allPath.push_back(curStr); return; } for(int i = curIdx; i < s.size(); ++i) { if(isP[curIdx][i]) { curPath.push_back(curIdx); partitionUtil(s, isP, i+1, curPath, allPath); curPath.pop_back(); } } } vector
         
          
           > partition(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function int n = s.size(); vector
           
            
              > isP(n, vector
             
              (n, false)); for(int i = n-1; i >= 0; --i) { for(int j = i; j < n; ++j) { if(s[i] == s[j]) isP[i][j] = (j-1 <= i+1) || isP[i+1][j-1]; } } vector
              
               
                 > allPath; vector
                
                  curPath; partitionUtil(s, isP, 0, curPath, allPath); return allPath; }};
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://bmxti.baihongyu.com/