LeetCode Solution 139 - Word Break

Problem Statement

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

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of lowercase English letters.

Optimal Approach - Dynamic Programming (Bottom-Up)

The best way to solve this problem efficiently is using Dynamic Programming (DP) with a bottom-up approach.

Explanation:

1. Create a dp array of size s.length() + 1, initialized to false except dp[0] = true.
2. Iterate over s and check if any substring ending at the current index is in wordDict.
3. If found, update dp[i] to true.
4. Return dp[s.length()] as the result.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
};

Step-by-Step Explanation

1. Initialization:

   • Create a boolean dp array of size s.length() + 1, initialized to false.
   • Set dp[0] = true since an empty string is always segmentable.

2. Iterate Over Substrings:

   • For each i (1 to s.length()), check if s.substr(j, i-j) exists in wordDict.
   • If dp[j] is true and the substring exists in the dictionary, mark dp[i] as true.

3. Return Result:

   • If dp[s.length()] is true, return true, else return false.

Dry Run / Execution Steps

Example:

Input: s = "leetcode", wordDict = ["leet", "code"]

DP Table Calculation:

dp[0]  = true  (Base case)
dp[1]  = false
dp[2]  = false
dp[3]  = false
dp[4]  = true   ("leet" found in dict)
dp[5]  = false
dp[6]  = false
dp[7]  = false
dp[8]  = true   ("code" found in dict)

Output: true

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Very slow for large inputs
Backtracking with Memoization	O(n^2)	O(n)	Still slower compared to DP
Bottom-Up DP (Iterative)	O(n^2)	O(n)	Best for performance and readability
Trie-Based Approach	O(n * m)	O(n * m)	More complex but useful for large dictionaries

Best Solution & Why It’s Best

The bottom-up DP approach is the most efficient because:

1. It avoids recursion overhead.
2. It has a predictable time complexity of O(n^2).
3. It guarantees the optimal solution.

Complexity Analysis

• Time Complexity: O(n^2) (nested loops checking substrings)
• Space Complexity: O(n + m) (DP array + word dictionary storage)

Conclusion

• The best approach is Bottom-Up Dynamic Programming.
• Alternative approaches like recursion or memoization fail in efficiency.
• Recommended practice problems:
  • Concatenated Words (LeetCode 472)
  • Word Break II (LeetCode 140)
  • Palindrome Partitioning (LeetCode 131)