74. Word Break

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        dp = [True] + [False] * len(s)      # dp[i]: s[:i] can be segmented
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[len(s)]

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];   // dp[i]: s[0..i) can be segmented
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++)
            for (int j = 0; j < i; j++)
                if (dp[j] && words.contains(s.substring(j, i))) { dp[i] = true; break; }
        return dp[s.length()];
    }
}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);   // dp[i]: s[0..i) can be segmented
        dp[0] = true;
        for (size_t i = 1; i <= s.size(); i++)
            for (size_t j = 0; j < i; j++)
                if (dp[j] && words.count(s.substr(j, i - j))) { dp[i] = true; break; }
        return dp[s.size()];
    }
};

function wordBreak(s, wordDict) {
  const words = new Set(wordDict), dp = new Array(s.length + 1).fill(false); // dp[i]: s[0..i) can be segmented
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && words.has(s.slice(j, i))) { dp[i] = true; break; }
  return dp[s.length];
}