1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    bool result;
    bool letters[26];
    bool wordBreak(string s, unordered_set<string> &dict) {
        result = false;
        for(int i = 0;i < 26;i++)
            letters[i] = false;
        for(string it:dict) {
            for(int i = 0;i < it.length();i++) {
                letters[it[i] - 'a'] = true;
            }
        }
        for(int  i = s.length();i > 0;i--) {
            if(existLetters(string(s,0,i)) == false)return false;
            if(dict.find(string(s,0,i)) != dict.end()) {
                if(i == s.length())return true;
                else {
                    wordBreakStep(s,i,dict);
                }
            }
        }
        return result;
    }
private:
    bool existLetters(string s) {
        for(int i = 0;i < s.length();i++) {
            if(letters[s[i] - 'a'] == false)return false;
        }
        return true;
    }
    void wordBreakStep(string s,int start,unordered_set<string> &dict) {
        if(result == true)return;
        for(int i = s.length() - start;i > 0;i--) {
            if(existLetters(string(s,start,i)) == false)return;
            if(dict.find(string(s,start,i)) != dict.end()) {
                if(i == s.length()-start) {
                    result = true;
                    return;
                }
                else {
                    wordBreakStep(s,start + i,dict);
                }
            }
        }
    }
};