Word Break - CPP Solution

1. Introduction

This blog post focuses on solving the "Word Break" problem in C++, a classic problem often encountered in coding interviews. The problem involves checking whether a given string can be segmented into a sequence of dictionary words.

Problem

Given a string s and a dictionary of strings wordDict, we need to determine whether s can be segmented into a space-separated sequence of one or more dictionary words.

2. Solution Steps

1. Use dynamic programming to solve this problem.

2. Create a boolean array dp where dp[i] indicates whether the substring s[0..i-1] can be segmented into dictionary words.

3. Initialize dp[0] to true.

4. For each position in the string, check if the substring ending at that position can be segmented into words in the dictionary.

5. If a valid segmentation is found, set dp[i] to true.

6. Return the value of dp[s.length()].

3. Code Program

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

// Function to check if the string can be segmented into words from the dictionary
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(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] && dict.find(s.substr(j, i - j)) != dict.end()) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

int main() {
    vector<string> wordDict = {"leet", "code"};
    string s = "leetcode";
    cout << "Can segment: " << wordBreak(s, wordDict) << endl;
    return 0;
}

Output:

Can segment: 1

Explanation:

1. The input string "leetcode" is processed to check if it can be segmented into words from the dictionary ["leet", "code"].

2. The dynamic programming approach checks each substring and verifies if it can form a word in the dictionary.

3. The substring "leet" is found in the dictionary, setting dp[4] to true.

4. The process continues, and "code" is also found, leading to dp[8] being true.

5. The function returns true (represented as 1), indicating that the string can indeed be segmented into words from the dictionary.