How do you solve Word Break on LeetCode?

Word Break (LeetCode #139) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Dynamic programming can significantly reduce redundant calculations by storing results of subproblems.

What is the brute force solution for Word Break?

The brute force approach for Word Break is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach tries to break the string into all possible combinations of words from the dictionary. If any combination matches the entire string, we return true. This method is simple but inefficient due to its exponential time complexity. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Word Break?

Word Break uses the following concepts: Array, Hash Table, String, Dynamic Programming, Trie, Memoization. The recommended patterns to study are: Dynamic Programming, Backtracking.

What are the interview tips for Word Break?

Always clarify the problem statement and constraints before diving into coding. Discuss your thought process and approach with the interviewer. Consider both time and space complexity when presenting your solution.

What are common mistakes when solving Word Break?

Not considering edge cases like an empty string or dictionary. Failing to optimize the recursive solution, leading to timeouts.

#139

Word Break

Medium

ArrayHash TableStringDynamic ProgrammingTrieMemoizationDynamic ProgrammingBacktracking

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution uses dynamic programming to store results of subproblems, avoiding redundant calculations. We maintain a boolean array that tracks whether a substring can be segmented into valid words.

⚙️

Algorithm

5 steps

1Step 1: Create a boolean array dp of size n+1, initialized to false, where n is the length of the string s.
2Step 2: Set dp[0] to true, as an empty string can always be segmented.
3Step 3: Iterate through the string, and for each position, check all possible previous positions to see if the substring can be formed using the dictionary.
4Step 4: If a valid segmentation is found, update the dp array accordingly.
5Step 5: Return the value of dp[n] which indicates if the entire string can be segmented.

solution.py10 lines

1def wordBreak(s, wordDict):
2    wordSet = set(wordDict)
3    dp = [False] * (len(s) + 1)
4    dp[0] = True
5    for i in range(1, len(s) + 1):
6        for j in range(i):
7            if dp[j] and s[j:i] in wordSet:
8                dp[i] = True
9                break
10    return dp[len(s)]

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops, but we save space in the dp array. The space complexity is O(n) because we store results for each substring.

1Dynamic programming can significantly reduce redundant calculations by storing results of subproblems.
2Understanding the problem's constraints helps in choosing the right approach.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.