aboutsummaryrefslogtreecommitdiff
path: root/word_break.cpp
blob: aa580c9561c2076e81ce2d7a28d57602ba698686 (plain)
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
// 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
}