# Question

Formatted question description: https://leetcode.ca/all/139.html

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.

# Algorithm

### Recursion

The memory array memo[i] is designed to track whether the substring within the range [i, n] is segmentable. It is initialized to -1, indicating that the calculation has not yet been performed. If segmentation is possible, it is updated to 1; if not, to 0.

A start variable is employed to denote the beginning of the segment. This allows the recursive function to efficiently traverse from the start position using the memory array memo.

### Dynamic Programming (DP)

• A dictionary array is used to mark indices in the string, avoiding the need to try every possible substring combination.

A one-dimensional DP array dp[i] is utilized, where each element represents whether the substring in the range [0, i) is segmentable.

It’s important to note that the dp array’s length exceeds the string s’s length by one to accommodate the empty string scenario. dp[0] is initialized to true.

Traversal begins with two nested loops. Since there is no recursive function, it’s necessary to examine all substrings. The substring range [0, i) is divided into two parts at j: [0, j) and [j, i), where:

• The range [0, j) corresponds to dp[j], reflecting a previously calculated state.
• The range [j, i) is represented by s.substr(j, i-j), needing verification against the dictionary.

If both conditions are met (dp[j] is true and s.substr(j, i-j) is in the dictionary), dp[i] is set to true, and the loop breaks. This implies no further division by j is necessary for the [0, i) range, as it is confirmed to be segmentable. The function ultimately returns the last element of the dp array, signifying whether the entire string can be segmented.

# Code

• import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Word_Break {

/*
input - 1:
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

input - 2:
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

*/

public class Solution_dp {
public boolean wordBreak(String s, Set<String> dict) {

if (s == null || dict == null || dict.size() == 0)  return false;

int length = s.length();

// since both dfs and bfs not working, try dynamic programming here
// construct dp, dp[i] meaning position i-1 can from dict or not
boolean[] dp = new boolean[length + 1];
dp[0] = true; // @note: initiate

for (int i = 0; i < length + 1; i++) {

if (dp[i] == false)  {
continue;

} else { // if some previous dict word ending at index i-1

for (String each: dict) {

if (i + each.length() > length)  continue;

if (s.substring(i, i + each.length()).equals(each)) {

dp[i + each.length()] = true;
// i = i + each.length() - 1; // i++ later
// break;
}
}
}
}

return dp[length];
}
}

public class Solution_bfs_over_time {
public boolean wordBreak(String s, Set<String> wordDict) {

if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
return false;
}

// since dfs is not working, now try bfs. all valid word's substring enqueue
Queue<String> q = new LinkedList<>();

q.offer(s);

while (!q.isEmpty()) {

String current = q.poll();

// if (current.length() == 0) { // meaning all previoius matched in dict

//     return true;
// }

for (int i = 0; i < current.length(); i++) {

String sub = current.substring(0, i + 1);

if (wordDict.contains(sub)) {

if (s.endsWith(sub)) { // @note: here is key, I missed it and the last word keeps dequeue and enqueue, infinite looping
return true;
}

// q.offer(s.substring(i + 1)); // @note: mistake here, should be current.substring(), not s.substring()
q.offer(current.substring(i + 1));
}
}
}

return false;
}
}

public class Solution_dfs_over_time {

public boolean wordBreak(String s, Set<String> wordDict) {

// @note: here is contradictory somehow, maybe a separate helper method would be good
// if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
if (s == null || wordDict == null) {
return false;
}

if (s.length() == 0) {
return true;
}

// substring from index 0 to i, check if in wordDict
for (int i = 0; i < s.length(); i++) {
String sub = s.substring(0, i + 1);

if (wordDict.contains(sub)) {
boolean isBreakable = wordBreak(s.substring(i + 1), wordDict);

// just write out logic more clearly
if (isBreakable) {
return true;
}
}
}

return false;
}
}

}

//////

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && words.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}

• // OJ: https://leetcode.com/problems/word-break/
// Time: O(S^3)
// Space: O(S + W)
class Solution {
public:
bool wordBreak(string s, vector<string>& dict) {
unordered_set<string> st(begin(dict), end(dict));
int N = s.size();
vector<bool> dp(N + 1);
dp[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i && !dp[i]; ++j) {
dp[i] = dp[j] && st.count(s.substr(j, i - j));
}
}
return dp[N];
}
};

• class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)

# dp[j] meaining s from 0 to index=i-1~ is breakable
dp = [True] + [False] * n # so actually size is n+1
for i in range(1, n + 1):
dp[i] = any( (dp[j] and s[j:i] in words) for j in range(i) )
return dp[n]

#############

class Solution:
def wordBreak(self, s: str, wordDict: Set[str]) -> bool:
if not s or not wordDict:
return False

length = len(s)

# construct dp, dp[i] meaning position i-1 can from dict or not
dp[-1] meaning at last-index plus 1, checking up to last-index
dp = [False] * (length + 1)
dp[0] = True  # initiate

for i in range(length + 1):
if not dp[i]:
continue
for word in wordDict:
if i + len(word) > length:
continue
if s[i:i + len(word)] == word:
dp[i + len(word)] = True

return dp[length]

#############

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # i'th char in string, is good
for j in range(1, n + 1):
for i in range(j): # starting at 0, includng dp[0]
if dp[i] and s[i:j] in words:
dp[j] = True # j is exclusive, meaining True until index i-1
break
return dp[-1]

#############

class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False

def insert(self, w):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True

def search(self, w):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
return node.is_end

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# https://docs.python.org/3/library/functools.html#functools.cache
# creating a thin wrapper around a dictionary lookup for the function arguments
@cache
def dfs(s):
return not s or any(trie.search(s[:i]) and dfs(s[i:]) for i in range(1, len(s) + 1))

trie = Trie()
for w in wordDict:
trie.insert(w)
return dfs(s)

#############

class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
queue = [0]
ls = len(s)
lenList = [l for l in set(map(len, wordDict))]
visited = [0 for _ in range(0, ls + 1)]
while queue:
start = queue.pop(0)
for l in lenList:
if s[start:start + l] in wordDict:
if start + l == ls:
return True
if visited[start + l] == 0:
queue.append(start + l)
visited[start + l] = 1
return False


• func wordBreak(s string, wordDict []string) bool {
words := make(map[string]bool)
for _, word := range wordDict {
words[word] = true
}
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if dp[j] && words[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[n]
}

• public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
var words = new HashSet<string>(wordDict);
int n = s.Length;
var dp = new bool[n + 1];
dp[0] = true;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (dp[j] && words.Contains(s.Substring(j, i - j)))
{
dp[i] = true;
break;
}
}
}
return dp[n];
}
}

• function wordBreak(s: string, wordDict: string[]): boolean {
const words = new Set(wordDict);
const n = s.length;
const f: boolean[] = new Array(n + 1).fill(false);
f[0] = true;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j < i; ++j) {
if (f[j] && words.has(s.substring(j, i))) {
f[i] = true;
break;
}
}
}
return f[n];
}


• impl Solution {
pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
let words: std::collections::HashSet<String> = word_dict.into_iter().collect();
let mut f = vec![false; s.len() + 1];
f[0] = true;
for i in 1..=s.len() {
for j in 0..i {
f[i] |= f[j] && words.contains(&s[j..i]);
}
}
f[s.len()]
}
}