Sharing my C++ solution


  • 0
    T
    class Solution {
    private:
        void dfs(string s, int k, vector<vector<bool>> DP, vector<string>& temp, vector<vector<string>>& result)
        {
            int n = s.length();
            if(k==n)
            {
                result.push_back(temp);
                return;
            }
            
            int i;
            for(i=k; i<n; i++)
            {
                if(DP[k][i])
                {
                    temp.push_back(s.substr(k, i-k+1));
                    dfs(s, i+1, DP, temp, result);
                    temp.pop_back();
                }
            }
        }
        
        bool isPalindrome(string s, int i, int j)
        {
            int left = i;
            int right = j;
            int n = s.length();
            char str[n+1];
            strcpy(str, s.c_str());
            while(left<right)
            {
                if(str[left] != str[right])
                    return false;
                left++;
                right--;
            }
            return true;
        }
        
    public:
        vector<vector<string>> partition(string s) {
            int n = s.size();
            char str[n+1];
            strcpy(str, s.c_str());
            
            
            vector<vector<bool>> DP; // DP[i,j]: whether substring[i,......,j] is palindrome
            int i;
            DP.resize(n);
            for(i=0; i<n; i++)
                DP[i].resize(n, false);
            
            int j;
            for(i=0; i<n; i++)
                for(j=i; j<n; j++)
                    DP[i][j] = isPalindrome(s, i, j);
                
            int len;
            int start, end;
            for(len=3; len<n; len++)
            {
                for(i=0; i<n-len; i++)
                {
                    start = i;
                    end = i+len-1;
                    DP[start][end] = DP[start+1][end-1] && (str[start] == str[end]);
                }
            }
            
            // Depth-first search
            vector<vector<string>> result;
            vector<string> temp;
            dfs(s, 0, DP, temp, result);
            
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.