Algorithm

Problem Name: 139. Word Break

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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".
Note that you are allowed to reuse a dictionary word.
```

Example 3:

```Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
```

Constraints:

• `1 <= s.length <= 300`
• `1 <= wordDict.length <= 1000`
• `1 <= wordDict[i].length <= 20`
• `s` and `wordDict[i]` consist of only lowercase English letters.
• All the strings of `wordDict` are unique.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
bool search(char *s, int l, char **wordDict, int wordDictSize) {
int i;
char *word;
for (i = 0; i  <  wordDictSize; i ++) {
word = wordDict[i];
if (word && l == strlen(word) && !strncmp(s, word, l)) return true;
}
return false;
}
bool wordBreak(char* s, char** wordDict, int wordDictSize) {
int i, j, l;
bool *buff, *e, result;

l = strlen(s);

buff = calloc((l + 1), sizeof(bool));
//assert(buff);

buff[0] = true;
e = &buff[1];

for (i = 0; i  <  l; i ++) {
for (j = i; !e[i] && j >= 0; j --) {
e[i] = e[j - 1] && search(&s[j], i - j + 1, wordDict, wordDictSize);
}
}

result = e[l - 1];
free(buff);

return result;
}
``````
Copy The Code &

Input

cmd
s = "leetcode", wordDict = ["leet","code"]

Output

cmd
true

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
unordered_mapm;
unordered_map < string, bool>dp;
public:
bool wordBreak(string s, vector<string>& wordDict) {
for(auto x: wordDict) m[x]++;
return DFS(s);
}

bool DFS(string s){
if(dp.count(s)) return dp[s];
if(s.empty()) return true;
bool found = false;
for(int i = 1; i <= s.size() && !found; i++)
if(m.count(s.substr(0, i))) found |= DFS(s.substr(i)>;
dp[s] = found;
return found;
}
};
``````
Copy The Code &

Input

cmd
s = "leetcode", wordDict = ["leet","code"]

Output

cmd
true

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean wordBreak(String s, List wordDict) {
Set set = new HashSet<>(wordDict);
Queue < Integer> queue = new LinkedList<>();
int[] visited = new int[s.length()];
while (!queue.isEmpty()) {
int start = queue.remove();
if (visited[start] == 0) {
for (int end = start + 1; end  < = s.length(); end++) {
if (set.contains(s.substring(start, end))) {
if (end == s.length()) {
return true;
}
}
}
visited[start] = 1;
}
}
return false;
}
}
``````
Copy The Code &

Input

cmd
s = "applepenapple", wordDict = ["apple","pen"]

Output

cmd
true

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const wordBreak = function(s, wordDict) {
const map = new Map()
return helper(s, 0, new Set(wordDict), map)
};

function helper(str, idx, set, map) {
if(idx === str.length) return true
if(map.has(idx)) return map.get(idx)
let res = false
for(let i = idx; i < str.length; i++) {
const tmp = str.slice(idx, i + 1)
if(set.has(tmp)) {
const bool = helper(str, i + 1, set, map)
if(bool) {
res = true
break
}
}
}
map.set(idx, res>
return res
}
``````
Copy The Code &

Input

cmd
s = "applepenapple", wordDict = ["apple","pen"]

Output

cmd
true

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def wordBreak(self, s, wordDict):
rightmosts, words = [0], set(wordDict)
for i in range(1, len(s) + 1):
for last_index in rightmosts:
if s[last_index:i] in words:
rightmosts.append(i)
if i == len(s):
return True
break
return False
``````
Copy The Code &

Input

cmd
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output

cmd
false

#6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0139_WordBreak
{
public bool WordBreak(string s, IList < string> wordDict)
{
int minLength = int.MaxValue, maxLength = int.MinValue;
var map = new HashSet();
foreach (var item in wordDict)
{
maxLength = Math.Max(maxLength, item.Length);
minLength = Math.Min(minLength, item.Length);
}

var dp = new bool[s.Length];
var index = 0;
while (index  <  s.Length)
{
for (int length = minLength; index + length <= s.Length && length <= maxLength; length++)
if (map.Contains(s.Substring(index, length)))
dp[index + length - 1] = true;

var j = index;
var found = false;
while (j  <  s.Length)
if (dp[j++])
{
index = j;
found = true;
break;
}

if (!found) return false;
}

return dp[s.Length - 1];
}
}
}
``````
Copy The Code &

Input

cmd
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output

cmd
false