Word Break medium

Problem Statement

Given a string s and a dictionary of strings wordDict, determine 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: Return true because "leetcode" can be segmented as "leet code".

Example 2

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

Steps

1. Dynamic Programming Approach: We'll use dynamic programming to solve this problem efficiently. We create a boolean array dp of size s.length() + 1. dp[i] will be true if the substring s[0...i-1] can be segmented into words from wordDict, and false otherwise.

2. Base Case: dp[0] is true because an empty string can always be segmented (no words needed).

3. Iteration: We iterate through the string s from index 1 to s.length(). For each index i, we check if the substring s[j...i-1] (where j ranges from 0 to i-1) is a word in wordDict. If it is, and dp[j] is true (meaning the substring s[0...j-1] can be segmented), then we set dp[i] to true.

4. Result: Finally, dp[s.length()] will indicate whether the entire string s can be segmented.

Explanation

The dynamic programming approach avoids redundant computations by storing the results of subproblems. If we find that a substring can be segmented, we store this information in the dp array, and we can reuse this information later when processing longer substrings. This significantly improves the efficiency compared to a naive recursive approach, which would suffer from exponential time complexity due to repeated calculations.

Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); // Use a set for O(1) lookup
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true; // Base case: empty string can be segmented

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            string word = s.substr(j, i - j);
            if (wordSet.count(word) && dp[j]) {
                dp[i] = true;
                break; // Optimization: Once we find a segmentation, no need to check further
            }
        }
    }

    return dp[n];
}

int main() {
    string s1 = "leetcode";
    vector<string> wordDict1 = {"leet", "code"};
    cout << wordBreak(s1, wordDict1) << endl; // Output: true

    string s2 = "applepenapple";
    vector<string> wordDict2 = {"apple", "pen"};
    cout << wordBreak(s2, wordDict2) << endl; // Output: true

    string s3 = "catsandog";
    vector<string> wordDict3 = {"cats", "dog", "sand", "and", "cat"};
    cout << wordBreak(s3, wordDict3) << endl; //Output: false

    return 0;
}

Complexity

• Time Complexity: O(n^2), where n is the length of the string s. The nested loops iterate through all possible substrings.
• Space Complexity: O(n), due to the dp array. The unordered_set uses extra space but its size is limited by the size of wordDict.