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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare 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;
}
Input
s = "leetcode", wordDict = ["leet","code"]
Output
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;
}
};
Input
s = "leetcode", wordDict = ["leet","code"]
Output
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()];
queue.add(0);
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))) {
queue.add(end);
if (end == s.length()) {
return true;
}
}
}
visited[start] = 1;
}
}
return false;
}
}
Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
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
}
Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
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
Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
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)
{
map.Add(item);
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];
}
}
}
Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
false