Easy to understand DFS backtracking c++


  • 0
    S
    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<string> path;
            vector<vector<string>> res;
            dfs(s, 0, s.size(), path, res);
            return res;
        }
        
        void dfs(string &s, int i, int j, vector<string> &p, vector<vector<string>> &r) {
            if (i == j) {
                r.push_back(p);
                return;
            }
            
            for (int k=i; k < j; ++k) {
                if (is_palindr(s, i, k)) {
                    p.push_back(s.substr(i, k-i+1));
                    dfs(s, k+1, j, p, r);
                    p.pop_back();
                }
            }
            
        }
        
        bool is_palindr(string &m, int s, int e) {
            while (e > s) {
                if (m[e--] != m[s++]) return false;
            }
            return true;
        }
    };
    

Log in to reply
 

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