C++, DP+DFS beats 92.9%


  • 0
    T

    Two steps:

    • find all palindrome substrings
    • dfs to find all path
    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            int n = s.length();
            vector<vector<int>> dp(n, vector<int> (1, 1));
            //first find all palindroms
            for (int i = n - 2; i >= 0; i--) {
                if (s[i] == s[i + 1])
                    dp[i].push_back(2);
                for (auto j : dp[i + 1]) 
                    if (i + 1 + j < n && s[i + 1 + j] == s[i]) 
                        dp[i].push_back(j + 2);
            }
            vector<vector<string>> res;
            vector<string> cur;
            //dfs
            partition(dp, s, 0, res, cur);
            return res;
        }
        void partition(vector<vector<int>> & dp, string & str, int s, vector<vector<string>> & res, vector<string> & cur) {
            if (s == str.length()) {
                res.push_back(cur);
                return ;
            }
            for (auto i : dp[s]) {
                cur.push_back(str.substr(s, i));
                partition(dp, str, s + i, res, cur);
                cur.pop_back();
            }
        }
    };
    

Log in to reply
 

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