The Word Break problem involves determining if a given string can be segmented into a sequence of valid words from a dictionary. This is commonly solved using dynamic programming.
Problem Statement:
Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Example:
- Input:makefileCopy code
s = "leetcode" wordDict = ["leet", "code"] - Output:arduinoCopy code
trueExplanation: Since"leetcode"can be segmented as"leet code", the function returnstrue.
Approach:
- Dynamic Programming (DP):
- Use a boolean array
dp[]wheredp[i]indicates if the substrings[0..i-1]can be segmented into words from the dictionary. - Initialize
dp[0]totruebecause an empty string can always be segmented. - For each position
ifrom1ton, check all possible substringss[j..i-1]forj < i. Ifdp[j]istrueands[j..i-1]is in the dictionary, setdp[i]totrue. - The final answer will be in
dp[n], wherenis the length of the strings.
- Use a boolean array
Code Implementations in Multiple Languages:
1. C Code:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// Helper function to check if a string can be segmented into words from the dictionary
bool wordBreak(char *s, char **wordDict, int wordDictSize) {
int n = strlen(s);
// DP array to store if s[0..i] can be segmented
bool dp[n + 1];
memset(dp, 0, sizeof(dp));
dp[0] = true; // Empty string can always be segmented
// Convert wordDict into a hash set for O(1) lookups
bool wordDictSet[1000] = {0}; // Assuming wordDict size is less than 1000
for (int i = 0; i < wordDictSize; i++) {
wordDictSet[hashString(wordDict[i])] = true;
}
// Loop through each substring of s
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet[hashString(s + j)]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
int hashString(char *str) {
int hash = 0;
while (*str) {
hash = (hash * 31 + *str++) % 1000;
}
return hash;
}
int main() {
char *wordDict[] = {"leet", "code"};
int wordDictSize = 2;
char s[] = "leetcode";
if (wordBreak(s, wordDict, wordDictSize)) {
printf("true\n");
} else {
printf("false\n");
}
return 0;
}
2. Python Code:
def wordBreak(s, wordDict):
n = len(s)
# Create a DP array to store whether s[0..i] can be segmented
dp = [False] * (n + 1)
dp[0] = True # Empty string can always be segmented
# Create a set of words for faster lookup
word_set = set(wordDict)
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
# Test case
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) # Output: True
3. C++ Code:
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
bool wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.length();
vector<bool> dp(n + 1, false);
dp[0] = true; // Empty string can always be segmented
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
int main() {
unordered_set<string> wordDict = {"leet", "code"};
string s = "leetcode";
if (wordBreak(s, wordDict)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
4. Java Code:
import java.util.*;
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
// DP array to store whether s[0..i] can be segmented
boolean[] dp = new boolean[n + 1];
dp[0] = true; // Empty string can always be segmented
// Convert wordDict to a set for O(1) lookups
Set<String> wordSet = new HashSet<>(wordDict);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void main(String[] args) {
Solution solution = new Solution();
List<String> wordDict = Arrays.asList("leet", "code");
String s = "leetcode";
System.out.println(solution.wordBreak(s, wordDict)); // Output: true
}
}
5. C# Code:
using System;
using System.Collections.Generic;
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
int n = s.Length;
// DP array to store whether s[0..i] can be segmented
bool[] dp = new bool[n + 1];
dp[0] = true; // Empty string can always be segmented
// Convert wordDict to a hash set for O(1) lookups
HashSet<string> wordSet = new HashSet<string>(wordDict);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void Main(string[] args) {
Solution solution = new Solution();
List<string> wordDict = new List<string> { "leet", "code" };
string s = "leetcode";
Console.WriteLine(solution.WordBreak(s, wordDict)); // Output: true
}
}
6. JavaScript Code:
function wordBreak(s, wordDict) {
let n = s.length;
let dp = Array(n + 1).fill(false);
dp[0] = true; // Empty string can always be segmented
// Create a set of words for faster lookup
let wordSet = new Set(wordDict);
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
// Test case
let s = "leetcode";
let wordDict = ["leet", "code"];
console.log(wordBreak(s, wordDict)); // Output: true
Time and Space Complexity:
- Time Complexity: O(N2)O(N^2)O(N2), where
Nis the length of the strings. The reason is that we are iterating over all substrings ofsand checking for each if it’s in the dictionary. - Space Complexity: O(N)O(N)O(N), as we need a dynamic programming array
dp[]of size N+1N+1N+1 to store the results for subproblems.
Conclusion:
The Word Break problem is a classic dynamic programming problem where we maintain a dp[] array to track whether substrings of the given string can be segmented into valid words from the dictionary. The solution involves iterating over all substrings and checking if they exist in the dictionary, ensuring an efficient solution for string segmentation problems.