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 defined as whether the substring in the range [i, n] can be split, initialized to -1, which means that it has not been calculated, if it can be split, it is assigned a value of 1, otherwise it is 0.

Use a start variable to mark the position of the segment, so that the recursive function only needs to traverse from the start position and then the memory array memo.

DP

Use dict array to mark index in string
not trying every combination of string’s substring

A one-dimensional dp array, where dp[i] indicates whether the substrings in the range [0, i) can be split.

Note that the length of the dp array is 1 greater than the length of the s string because of the need to handle an empty string. Initialize dp[0] to true.

Then start traversal. Note that two for loops are needed to traverse, because there is no recursive function at this time, so we must traverse all the substrings, and divide the substrings in the range of [0, i) into two parts with j, [0, j) and [j, i)

where the range [0, j) is dp[j], and the range [j, i) is s.substr(j, ij),
where dp[j] is the previous state, which has been calculated already. You only need to look up whether s.substr(j, ij) exists in the dictionary.

If both are true, assign dp[i] to true and break off, so you don’t need to use j to divide the range of [0, i), because the range of [0, i) can be split. Finally returns the last value of the dp array.

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

139 - Word Break

Question

Algorithm

Recursion

DP

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Recursion

DP

Code

All Problems

All Solutions