Daily LeetCode Problems: Problem 139. Word Break
Breaking It Down: Solving the Word Break Problem
Introduction:
Welcome to another problem-solving article! In today’s edition, we’ll delve into problem 139 from LeetCode, titled “Word Break.” This problem challenges us to determine if a given string can be segmented into a sequence of words from a dictionary. We’ll carefully analyze the problem statement, devise an efficient approach, provide pseudocode for better understanding, explain the core concepts, and discuss the complexity analysis.
Problem Statement:
The problem presents us with a string s
and a dictionary wordDict
containing various words. Our goal is to determine whether the given string can be divided into a sequence of words from the dictionary. Importantly, the words in the dictionary can be reused multiple times to form the string.
Approach:
To solve this problem, we can use the dynamic programming approach. We’ll iterate through the given string s
and check if any prefix of s
can be segmented into words from the dictionary. We'll maintain a dynamic programming array to keep track of the segmentation possibilities for different prefixes of s
. Specifically, if a prefix of s
can be segmented into words from the dictionary, we'll mark that position in the DP array as True
.
Pseudocode:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # An empty string can always be segmented
wordSet = set(wordDict) # Convert wordDict to a set for faster lookups
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[n]
Explanation:
- We initialize a dynamic programming array
dp
wheredp[i]
indicates whether the substrings[:i]
can be segmented into words from the dictionary. - We mark the base case
dp[0]
asTrue
because an empty string can always be segmented. - We convert
wordDict
to a set calledwordSet
for faster lookups. - We iterate through the string
s
from left to right (indexi
) and check whether any prefix ofs
(substrings[:i]
) can be segmented into words from the dictionary. - To do this, we check all possible positions (index
j
) where we can split the substrings[:i]
into two parts:s[:j]
ands[j:i]
. - If
dp[j]
isTrue
(meanings[:j]
can be segmented) ands[j:i]
is found in thewordSet
, we updatedp[i]
toTrue
and break the inner loop. - Finally, we return the value of
dp[n]
, wheren
is the length of the strings
.
Complexity Analysis:
- Time complexity: The dynamic programming approach iterates through each position in the string
s
, and for each position, it checks the substrings against thewordSet
. Therefore, the time complexity is O(n^2), where n is the length of the input string. - Space complexity: We use an additional dynamic programming array
dp
of sizen+1
and awordSet
of sizek
, wherek
is the number of words in the dictionary. Thus, the space complexity is O(n + k).
Full Solution
Python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
@functools.lru_cache(None)
def wordBreak(s: str) -> bool:
if s in wordSet:
return True
return any(s[:i] in wordSet and wordBreak(s[i:]) for i in range(len(s)))
return wordBreak(s)
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s, new HashSet<>(wordDict), new HashMap<>());
}
private boolean wordBreak(final String s, Set<String> wordSet, Map<String, Boolean> memo) {
if (memo.containsKey(s))
return memo.get(s);
if (wordSet.contains(s)) {
memo.put(s, true);
return true;
}
// 1 <= prefix.length() < s.length()
for (int i = 1; i < s.length(); ++i) {
final String prefix = s.substring(0, i);
final String suffix = s.substring(i);
if (wordSet.contains(prefix) && wordBreak(suffix, wordSet, memo)) {
memo.put(s, true);
return true;
}
}
memo.put(s, false);
return false;
}
}
C++
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
return wordBreak(s, {wordDict.begin(), wordDict.end()}, {});
}
private:
bool wordBreak(const string& s, const unordered_set<string>&& wordSet,
unordered_map<string, bool>&& memo) {
if (wordSet.count(s))
return true;
if (const auto it = memo.find(s); it != memo.cend())
return it->second;
// 1 <= prefix.length() < s.length()
for (int i = 1; i < s.length(); ++i) {
const string& prefix = s.substr(0, i);
const string& suffix = s.substr(i);
if (wordSet.count(prefix) && wordBreak(suffix, move(wordSet), move(memo)))
return memo[s] = true;
}
return memo[s] = false;
}
};
Conclusion:
In this article, we tackled LeetCode problem 139, “Word Break.” We examined the problem statement, devised an efficient dynamic programming approach, provided pseudocode to illustrate the implementation, and discussed the time and space complexities. By leveraging dynamic programming, we efficiently determined whether a given string can be segmented into a sequence of words from a dictionary. Continue practicing similar problems to enhance your algorithmic skills. Stay tuned for more exciting LeetCode challenges in our daily series. Happy coding!