MediumCoding

Word Break

Asked at

Meta

ServiceNow

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words otherwise return false.

Note : The same word in dictionary can be used multiple times in segmentation.

Input : s = "takeuforward" , wordDict = ["take" , "forward" , "you", "u"] Output : true Explanation : Return true because "takeuforward" can be segmented as "take" , "u" , "forward".

Input : s = "applepineapple" , wordDict = ["apple"] Output : false Explanation : Return false because "applepineapple" can be segmented as "apple" , "pine" , "apple" but here we do not have "pine" word in dictionary.

Input : s = "catsanddogs" , wordDict = ["and" , "dogs" ,"cats", "animals"]

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist only of English lowercase letters.
All strings in wordDict are unique.

cpp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // Your code goes here
    }
};

java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Your code goes here
    }
}

python

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        # Your code goes here

javascript

class Solution {
    wordBreak(s, wordDict) {
        // Your code goes here
    }
}

csharp

class Solution {
    public bool WordBreak(string s, List<string> wordDict) {
        
    }
}

func wordBreak(s string, wordDict []string) bool {

}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Put dictionary words in a hash set.
02Let dp[i] mean prefix s[0..i) is segmentable.
03For each reachable prefix, try valid next word endings.
04Return dp[n] and explain repeated-word allowance.

Reference answer

Use dynamic programming over prefix boundaries. Let dp[i] mean the first i characters of s can be segmented; initialize dp[0]=true. For each end index i, check a prior j with dp[j] true and s[j..i) in a hash set. If found, set dp[i] true and stop that inner loop. The answer is dp[n]. Reusing a dictionary word is naturally allowed because each transition is independent. The direct implementation is O(n^2) substring checks, with O(n) DP space; limit j by the maximum word length or use a trie to reduce wasted checks. Be explicit about substring allocation costs in the language used. Test empty s, an empty dictionary, overlapping words such as cats/cat, and a string whose final suffix fails. Do not use greedy longest-word matching because it can block a valid later split.

Then expect these follow-ups

How does a trie change the transitions?
Tests: tries
Why can greedy matching fail?
Tests: counterexamples

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question