140. word break ii

Word Break https://leetcode.com/problems/word-break/140.word break ii https://leetcode.com/problems/word-break-ii/dfs 가지치기, 약간 dp 느낌으로.

1. 가장 널리 퍼지는 방법은 먼저 DP로 분할이 가능한지 판단한 다음에 dfs로 방안을 훑어본다.

class Solution {
public:
    string m_str;
    unordered_set m_wordDict;
    vector wordBreak(string s, unordered_set& wordDict) {
        m_str = s;
        m_wordDict = wordDict;
        string now = "";
        vector result;
        result.clear();
        
        int n = s.length();
        int dictsize = wordDict.size();
        if(dictsize == 0) {
            return result;
        }
        if(n == 0) {
            result.push_back("");
            return result;
        }
        
        bool f[n + 1];
        f[0] = true;
        for(int i = 1; i <= n; i++) {
            f[i] = false;
            for(int j = 0; j < i; j++) {
                if(f[j] && wordDict.find(s.substr(j,i-j))!=wordDict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        if(f[n] == false) {
            return result;
        }
        
        wordBreakRecursion(result, now, f, 1);
        return result;
    }
    
    void wordBreakRecursion(vector& result, string now, bool * f,int charnum){
        if(charnum == m_str.length() + 1){
            now = now.substr(0, now.length() - 1);
            result.push_back(now);
            return;
        }
        for(int i = charnum; i <= m_str.length(); i++) {
            //cout<

2. 순수 dfs, 회time limit exceed

class Solution {
    void helper(vector &res, string now, string & s, int pos, unordered_set& wordDict) {
        if(pos == s.size()) {
            res.push_back(now.substr(1));
            return;
        }
        for(int i = pos; i < s.size(); i++) {
            string sub = s.substr(pos,i - pos + 1);
            if(wordDict.find(sub) != wordDict.end()) {
                helper(res,now + " " + sub,s,i+1,wordDict);
            }
        }
    }
public:
    vector wordBreak(string s, unordered_set& wordDict) {
        vector res;
        helper(res,"",s,0,wordDict);
        return res;
    }
};

3. 순수 dp, memory limit exceeded

class Solution {
public:
    vector wordBreak(string s, unordered_set& wordDict) {
        int n = s.size();
        vector dp(n+1,false);
        vector > res(n+1,vector());
        dp[0] = true;
        res[0].push_back("");
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                string t = s.substr(j, i - j + 1);
                if(dp[j] && wordDict.find(t) != wordDict.end()) {
                    dp[i+1] = true;
                    for(int k = 0; k < res[j].size(); k++)
                        res[i+1].push_back(res[j][k] + " " + t);
                }
            }
        }
        for(int k = 0; k < res[n].size(); k++) {
            res[n][k] = res[n][k].substr(1);
        }
        return res[n];
    }
};    

4.discuss의 해법, 가지치기 dfs, 나는 그것과 dp 방법이 사용하는 메모리의 차이가 어디에 있는지 모르겠다. 생각해 보자.이것은 dfs가 마지막에 새로운 조합을 만들 수 있다는 것을 발견하고 하나의word를mem에 넣는 것이다. 그리고 나의 dp는 도착한 후에 마지막에 도착하지 않는word도mem에 넣었기 때문에 초과했다.

class Solution {
    vector> mem;
    vector visit;
    void DFS(string& s, unordered_set& wordDict, int pos) {
        visit[pos] = 1;
        for (int i = pos + 1; i <= s.size(); ++i) {
            if (wordDict.find(s.substr(pos, i - pos)) != wordDict.end()) {
                if (i == s.size()) {
                    mem[pos].push_back(s.substr(pos, i - pos));
                    continue;
                }
                if (!visit[i])
                    DFS(s, wordDict, i);
                for (auto& str : mem[i]) 
                    mem[pos].push_back(s.substr(pos, i - pos) + " " + str);
            }
        }
    }

public:
    vector wordBreak(string s, unordered_set& wordDict) {
        visit.resize(s.size());
        mem.resize(s.size());
        DFS(s, wordDict, 0);
        vector answ = mem[0];
        mem.clear();
        visit.clear();
        return answ;
    }
};