LeetCode Solution 139 - Word Break

Problem Statement:

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.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple".

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Optimal Approach:

The most efficient approach to solving this problem is Dynamic Programming (DP). We use a boolean DP array where dp[i] is true if s[0...i-1] can be segmented using words from wordDict.

Steps:

1. Create a DP array dp of size n + 1 (where n = s.length()), initialized to false.
2. Set dp[0] = true, meaning an empty string can always be segmented.
3. Iterate through the string and check all possible substrings against wordDict.
4. If dp[j] is true and s[j...i] is in wordDict, set dp[i] = true.

C++ Solution:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

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. Convert wordDict into an unordered set for O(1) lookup time.
2. Initialize the DP array where dp[0] = true (empty string case).
3. Iterate through the string, checking all substrings s[j...i].
4. If dp[j] is true and s[j...i] exists in wordDict, set dp[i] = true.
5. Return dp[s.length()], which tells whether s can be segmented.

Dry Run Example:

Input:

s = "applepenapple";
wordDict = ["apple", "pen"];

Execution:

Index (i)	Substring Checked	dp[i]
5	"apple"	true
8	"pen"	true
13	"apple"	true

Output: true

Alternative Approaches:

1. Brute Force (Backtracking):

• Try all possible partitions.
• Time Complexity: O(2^n) (Exponential)
• Space Complexity: O(n) (Recursion Depth)

2. BFS (Graph-based Solution):

• Treat the problem as a graph where nodes represent valid partitions.
• Time Complexity: O(n^2) in worst case.
• Space Complexity: O(n)

Best Solution & Why:

Approach	Time Complexity	Space Complexity	Why?
Brute Force	O(2^n)	O(n)	Too slow for large inputs
BFS	O(n^2)	O(n)	Uses queue, not optimal
DP	O(n^2)	O(n)	Best balance of time and space

Complexity Analysis of DP Solution:

• Time Complexity: O(n^2) → Two nested loops iterating over substrings.
• Space Complexity: O(n) → DP array storing n+1 boolean values.

Conclusion:

• DP is the best approach as it efficiently checks all partitions with O(n^2) complexity.
• Similar Problems for Practice:
  • Word Break II
  • Concatenated Words
  • Longest Word in Dictionary