Word Break

Given a string s and a dictionary of words dict, you need to determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Sample Input:

s = “theking”
dict = [“the”, “king”]

Expected Output:

true

Explanation:
The string “theking” can be segmented into “the” and “king,” both of which are present in the dictionary.

Time and Space Complexity:

The time complexity of the solution will be O(n^2), where n is the length of the input string s.

The space complexity will be O(n), where n is the length of the input string s.

C++ Solution:

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

using namespace std;

bool wordBreak(string s, unordered_set<string>& wordDict) {
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            if (dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
    string s = "leetcode";
    unordered_set<string> wordDict = {"leet", "code"};

    if (wordBreak(s, wordDict)) {
        cout << "The string can be segmented.\n";
    } else {
        cout << "The string cannot be segmented.\n";
    }

    return 0;
}

In this solution, we use dynamic programming to keep track of whether a substring of s can be formed by words in the dictionary. The dp array is used to store whether the substring ending at index i can be segmented or not. We initialize dp[0] to true because an empty string is always considered segmented.

We then iterate through each index i of the string and look back at all possible substrings ending at i. If any of these substrings can be segmented (i.e., dp[j] is true) and the remaining substring (from j to i) is present in the dictionary, we update dp[i] to true. Finally, the value of dp[n] will tell us whether the entire string s can be segmented or not.

The output will be: “The string can be segmented.”