1
/**
2
 * @param {string} s
3
 * @param {string[]} wordDict
4
 * @return {boolean}
5
 */
6
var wordBreak = function (s, wordDict) {
7
  var dp = new Array(s.length + 1).fill(false);
8
  dp[s.length] = true;
9

10
  for (var i = s.length - 1; i >= 0; i--) {
11
    for (const word of wordDict) {
12
      if (
13
        i + word.length <= s.length &&
14
        s.substring(i, i + word.length) === word
15
      ) {
16
        dp[i] = dp[i + word.length];
17
      }
18

19
      if (dp[i]) break;
20
    }
21
  }
22

23
  return dp[0];
24
};
25

26
// naive approach, take each word from the set and check if they match
27
/// O(n ^ 2 * m)
28
// considering m as the dictionary size
29
/*
30
var dict = new Set();
31
for (const word of wordDict) {
32
    dict.add(word);
33
}
34

35
return canSegment(s, dict, 0);
36

37
function canSegment (str, dict, index) {
38
    if (index >= str.length) return true;
39

40
    var success = false;
41
    for (const word of dict.values()) {
42

43
        if ((index + word.length) <= str.length) {
44
            var substring = str.substring(index, index + word.length);
45

46
            if (dict.has(substring)) {
47
                success = success | canSegment(str, dict, index + word.length);
48
            }
49
        }
50
    }
51

52
    return success;
53
}
54
*/