Word Break Problem | (Trie solution) Medium 0 attempts
GeeksforGeeks ↗

Word Break Problem | (Trie solution)

Medium Tries GeeksforGeeks

Given a string s and a dictionary of words, determine if s can be segmented into space-separated dictionary words.

Example: s = "leetcode", wordDict = ["leet","code"] → true

Sample Input
—
Sample Output
—
Constraints
  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
Topics
Tries

DP with Trie

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

Time: O(n² × k) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript