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

Appended Solution 2: Translated Upstream Explanation

We first store the words in $wordDict$ into the prefix tree, and then use dynamic programming to solve them.

We define $f[i]$ to mean splitting from the $i$ character of the string $s$ backwards, whether it can be split into words in $wordDict$, initially $f[n]=true$, and the rest are $false$. The answer is $f[0]$.

Next, we enumerate $i$ from large to small, and for each $i$, we start from $i$ and split backwards. If $s[i:j]$ is in the prefix tree, and $f[j+1]=true$, then $f[i]=true$.

Time complexity $O(n^2)$, space complexity $O(n)$. Where $n$ is the length of the string $s$.

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];
    }
}


// Solution 2
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Trie trie = new Trie();
        for (String w : wordDict) {
            trie.insert(w);
        }
        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[n] = true;
        for (int i = n - 1; i >= 0; --i) {
            Trie node = trie;
            for (int j = i; j < n; ++j) {
                int k = s.charAt(j) - 'a';
                if (node.children[k] == null) {
                    break;
                }
                node = node.children[k];
                if (node.isEnd && f[j + 1]) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[0];
    }
}

class Trie {
    Trie[] children = new Trie[26];
    boolean isEnd = false;

    public void insert(String w) {
        Trie node = this;
        for (int i = 0; i < w.length(); ++i) {
            int j = w.charAt(i) - 'a';
            if (node.children[j] == null) {
                node.children[j] = new Trie();
            }
            node = node.children[j];
        }
        node.isEnd = true;
    }
}

// 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];
    }
};


// Solution 2
class Trie {
public:
    vector<Trie*> children;
    bool isEnd;
    Trie()
        : children(26)
        , isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char c : word) {
            c -= 'a';
            if (!node->children[c]) node->children[c] = new Trie();
            node = node->children[c];
        }
        node->isEnd = true;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        for (auto& w : wordDict) {
            trie.insert(w);
        }
        int n = s.size();
        vector<bool> f(n + 1);
        f[n] = true;
        for (int i = n - 1; ~i; --i) {
            Trie* node = &trie;
            for (int j = i; j < n; ++j) {
                int k = s[j] - 'a';
                if (!node->children[k]) {
                    break;
                }
                node = node->children[k];
                if (node->isEnd && f[j + 1]) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[0];
    }
};

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


# Solution 2
class Trie:
    def __init__(self):
        self.children: List[Trie | None] = [None] * 26
        self.isEnd = False

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


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        trie = Trie()
        for w in wordDict:
            trie.insert(w)
        n = len(s)
        f = [False] * (n + 1)
        f[n] = True
        for i in range(n - 1, -1, -1):
            node = trie
            for j in range(i, n):
                idx = ord(s[j]) - ord('a')
                if not node.children[idx]:
                    break
                node = node.children[idx]
                if node.isEnd and f[j + 1]:
                    f[i] = True
                    break
        return f[0]



# Solution 1 (additional implementation)
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            f[i] = any(f[j] and s[j:i] in words for j in range(i))
        return f[n]

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]
}


// Solution 2
type trie struct {
	children [26]*trie
	isEnd    bool
}

func newTrie() *trie {
	return &trie{}
}

func (t *trie) insert(w string) {
	node := t
	for _, c := range w {
		c -= 'a'
		if node.children[c] == nil {
			node.children[c] = newTrie()
		}
		node = node.children[c]
	}
	node.isEnd = true
}

func wordBreak(s string, wordDict []string) bool {
	trie := newTrie()
	for _, w := range wordDict {
		trie.insert(w)
	}
	n := len(s)
	f := make([]bool, n+1)
	f[n] = true
	for i := n - 1; i >= 0; i-- {
		node := trie
		for j := i; j < n; j++ {
			k := s[j] - 'a'
			if node.children[k] == nil {
				break
			}
			node = node.children[k]
			if node.isEnd && f[j+1] {
				f[i] = true
				break
			}
		}
	}
	return f[0]
}

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];
    }
}


// Solution 2
public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        Trie trie = new Trie();
        foreach (string w in wordDict) {
            trie.Insert(w);
        }
        int n = s.Length;
        bool[] f = new bool[n + 1];
        f[n] = true;
        for (int i = n - 1; i >= 0; --i) {
            Trie node = trie;
            for (int j = i; j < n; ++j) {
                int k = s[j] - 'a';
                if (node.Children[k] == null) {
                    break;
                }
                node = node.Children[k];
                if (node.IsEnd && f[j + 1]) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[0];
    }
}

class Trie {
    public Trie[] Children { get; set; }
    public bool IsEnd { get; set; }

    public Trie() {
        Children = new Trie[26];
        IsEnd = false;
    }

    public void Insert(string word) {
        Trie node = this;
        foreach (char c in word) {
            int i = c - 'a';
            if (node.Children[i] == null) {
                node.Children[i] = new Trie();
            }
            node = node.Children[i];
        }
        node.IsEnd = true;
    }
}

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];
}


// Solution 2
function wordBreak(s: string, wordDict: string[]): boolean {
    const trie = new Trie();
    for (const w of wordDict) {
        trie.insert(w);
    }
    const n = s.length;
    const f: boolean[] = new Array(n + 1).fill(false);
    f[n] = true;
    for (let i = n - 1; i >= 0; --i) {
        let node: Trie = trie;
        for (let j = i; j < n; ++j) {
            const k = s.charCodeAt(j) - 97;
            if (!node.children[k]) {
                break;
            }
            node = node.children[k];
            if (node.isEnd && f[j + 1]) {
                f[i] = true;
                break;
            }
        }
    }
    return f[0];
}

class Trie {
    children: Trie[];
    isEnd: boolean;

    constructor() {
        this.children = new Array(26);
        this.isEnd = false;
    }

    insert(w: string): void {
        let node: Trie = this;
        for (const c of w) {
            const i = c.charCodeAt(0) - 97;
            if (!node.children[i]) {
                node.children[i] = new Trie();
            }
            node = node.children[i];
        }
        node.isEnd = true;
    }
}

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()]
    }
}

139 - Word Break

Question

Algorithm

Recursion

Dynamic Programming (DP)

Code

Appended Solution 2: Translated Upstream Explanation

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Recursion

Dynamic Programming (DP)

Code

Appended Solution 2: Translated Upstream Explanation

All Problems

All Solutions