[LeetCode] 139. Word Break

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

Word Break - LeetCode

 

문제 접근법 : 

Word Break2 문제와 유사합니다. 오히려 이게 더난이도가 Medium으로 되어있고 Word Break2가 hard로 되어있습니다.

그치만 개인적으로 전 이게 더어렵게 느껴졌었죠 ㅠ.ㅠ

 

WordBreak2와 같이 s를 기준으로 부분문자열을 이용한 재귀함수로 worddict를 이용해서 만들수있는지 없는지 확인합니다.

그치만 경우의수가 너무많으니 메모이제이션 기법을이용해서 풀어야합니다.

 

소스코드 :

class Solution {
public:
vector<int> dp;
int dfs(string &s,set<string> &m,int idx=0){
    if(idx>=s.size()) return true;

    int &cache = dp[idx];
    if(cache!=-1)return cache;
    cache = 0;
    for(int i=idx;i<s.size();i++){
        if(m.count(s.substr(idx,i+1-idx))&&dfs(s,m,i+1)){
            return cache=true;
        }
    }
    return cache;
}
bool wordBreak(string s, vector<string>& wordDict) {
    set<string> m(wordDict.begin(),wordDict.end());
    dp = vector<int>(s.size(),-1);
    return dfs(s,m);
}
};

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.