Letcode 문제 풀이--Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s =  "leetcode" , dict =  ["leet", "code"] .
Return true because  "leetcode"  can be segmented as  "leet code" .
문제풀이 사고방식: 이런 문자열이 일치하는 문제는 일반적으로 동적 기획이나 귀속으로 해결된다.

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        if(!n) return true;
        if(wordDict.empty()) return false;
        
        vector<bool> D(n+1,false);
        D[0] = true;
        
        int longestWord = 0;
        for(auto word : wordDict){
            longestWord = max(longestWord, (int)word.size());
        }
        
        for(int i=1; i<=n; i++){
            int k = max(0,(i-longestWord));
            for(int j=i-1; j>=k; j--){
                if(D[j]){
                    string t = s.substr(j,i-j);
                    if(wordDict.find(t)!=wordDict.end()){
                        D[i] = true;
                        break;
                    }
                }
            }
        }
        return D[n];
        
    } 
};

동적 기획:0ms

class Solution {
public:
     bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        if(!n) return true;
        if(wordDict.empty()) return false;
        for(int i=n-1; i>=0; i--){
            if(wordDict.find(s.substr(i))!=wordDict.end()) break;
            if(i==0) return false;
        }
        return findwordBreak(s,wordDict);
    }
    
    bool findwordBreak(string s, unordered_set<string>& wordDict){
        int n = s.size();
        if(n==0){
            return true;
        }
        for(int i=1; i<=n; i++){
            string t = s.substr(0,i);
            if(wordDict.find(t)!=wordDict.end()){
                if(findwordBreak(s.substr(i), wordDict)) return true;
            }
        }
        return false;
    }
};

귀속:0ms