Welcome to Subscribe On Youtube

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

All Problems

All Solutions