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

Word Break Problem | (Trie solution)

Medium Tries GeeksforGeeks

You're given a string s and a dictionary of words wordDict. Decide whether s can be broken up into a sequence of one or more dictionary words placed back to back, where the same dictionary word may be reused as many times as needed.

Input Format
Implement wordBreak(s, wordDict). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s = "leetcode"
wordDict = ["leet","code"]
Output
true

Example 2

Input
s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
Output
false
Constraints
  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
Test Cases (2)
Case 1
Args: ["leetcode",["leet","code"]] Expected: true
Case 2
Args: ["catsandog",["cats","dog","sand","and","cat"]] Expected: false
Topics
Tries

DP with a Hash Set

javascript
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³) worst case including substring creation and hashing | Space: O(n + D), where D is total dictionary size

Saved in this browser only. Private to you.

JavaScript