diff options
Diffstat (limited to 'other/word_break.cpp')
-rw-r--r-- | other/word_break.cpp | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/other/word_break.cpp b/other/word_break.cpp new file mode 100644 index 0000000..aa580c9 --- /dev/null +++ b/other/word_break.cpp @@ -0,0 +1,38 @@ +// 139. Word Break +#include "leetcode.h" + +/* + * given a string 's' and a dictionary of strings 'word_dict', return 'true' if + * 's' can be segmented into a space-separated sequence of one or more + * dictionary words. note that the same word in the dictionary may be reused + * multiple times in the segmentation. + */ + +class Solution { +public: + bool wordBreak(string s, unordered_set<string> &word_dict) { + if (!word_dict.size()) + return false; + vector<bool> dp(s.size() + 1, false); + dp[0] = true; + for (int i = 1; i <= s.size(); i++) + for (int j = i - 1; j >= 0; j--) + if (dp[j]) { + string word = s.substr(j, i - j); + if (word_dict.find(word) != word_dict.end()) { + dp[i] = true; + break; + } + } + return dp[s.size()]; + } +}; + +int main() { + Solution obj; + unordered_set<string> wd1 = {"leet", "code"}, wd2 = {"apple", "pen"}, + wd3 = {"cats", "dog", "sand", "and", "cat"}; + printf("%d\n", obj.wordBreak("leetcode", wd1)); // expect: 1 + printf("%d\n", obj.wordBreak("applepenapple", wd2)); // expect: 1 + printf("%d\n", obj.wordBreak("catsandog", wd3)); // expect: 0 +} |