8ms c++ dp+dfs solution


  • 0
    E
        vector<vector<string>> partition(string s) {
            int n = s.size();
            vector<vector<string>> result;
            if(n == 0) {
                return result;
            }
            // First dp to find all palindromes
            // isPalindromes[i][j]: is substring s(i,j) palindrome
            bool **isPalindrome = new bool*[n];
            for(int i = 0; i < n; i++) {
                isPalindrome[i] = new bool[n];
            }
            for(int i = 1; i < n; i++) {
                isPalindrome[i][i-1] = true;
            }
            for(int i = 0; i < n; i++) {
                isPalindrome[i][i] = true;
            }
            for(int length = 2; length <= n; length++) {
                for(int i = 0; i <= (n - length); i++) {
                    isPalindrome[i][i+length-1] = isPalindrome[i+1][i+length-2] && (s[i] == s[i+length-1]);
                }
            }
            vector<string> tmp;
            // Then dfs to find all partitions
            findPartitions(s, 0, tmp, result, isPalindrome);
            
            for(int i = 0; i < n; i++) {
                delete [] isPalindrome[i];
            }
            delete [] isPalindrome;
            return result;
        }
        
        void findPartitions(string s, int k, vector<string>& tmp, vector<vector<string>>& partitions, bool **isPalindrome) {
            int n = s.size();
            if(k == n) {
                partitions.push_back(tmp);
                return;
            }
            for(int i = k; i < n; i++) {
                if(isPalindrome[k][i]) {
                    tmp.push_back(s.substr(k, i-k+1));
                    findPartitions(s, i+1, tmp, partitions, isPalindrome);
                    tmp.pop_back();
                }
            }
        }

Log in to reply
 

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