[LeetCode] 140. Word Break II

문제 URL : https://leetcode.com/problems/word-break-ii/

Word Break - LeetCode

 

문제 접근법 : 

wordDict를 이용해서 문자열 s를 만들수있는 모든 경우를 구하는겁니다.

문자열s의 길이가 20밖에 안되니

재귀함수를 이용해서 wordDict를 이용하는것이아닌 s의 부분문자함수를 이용해서

구하는것이 훨씬더 빠르고 명료하게 만들어질수있습니다.

 

소스코드 : 

 

class Solution {
public:
vector<string> v;
void dfs(string s,set<string>&m,string res=""){
    if(s.size()==0){
        res.pop_back();
        v.push_back(res);
        return;
    }
    for(int i=0;i<s.size();i++){
        string t = s.substr(0,i+1);
        if(m.count(t)){
            dfs(s.substr(i+1),m,res+t+" ");
        }
    }
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
    set<string> m(wordDict.begin(),wordDict.end());
    dfs(s,m);
    return v;
}
};