# 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.