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

Hiring now

ServiceNow has 794 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer, Search Infrastructure - Moveworks
Mountain View, CALIFORNIA, United States
Staff Software Engineer, AI Native Engineering, Integrations
Hyderabad, India
Software Engineer
Santa Clara, CALIFORNIA, United States

Or practice this question first

Next question