139. Word Break (Dynamic Programming) 20.3.27 Medium

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 
determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
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


Solution no.1: ------------------------------ Brutal Force DFS but TLE error
--------------------------------------------- O(n^n) T, O(n) S
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not wordDict:
            return None
        return self.BF(s, wordDict, 0)
    
    def BF(self, s, wordDict, start):
        if start == len(s):
            return True
        for end in range(start, len(s) + 1):
            if s[start:end] in wordDict and self.BF(s, wordDict, end):
                return True
        return False

Solution no.2: ----------------------------------------- Recursion with memo
--------------------------------------------- O(n^2) T, O(n) S
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not wordDict:
            return None
        self.memo = {}
        return self.BF(s, wordDict, 0)
    
    def BF(self, s, wordDict, start):
        if start == len(s):
            return True
        if start in self.memo:
            return self.memo[start]
        for end in range(start, len(s) + 1):
            if s[start:end] in wordDict and self.BF(s, wordDict, end):
                self.memo[start] = True
                return True
        self.memo[start] = False
        return False

Solution: ----------------------------------- Dynamic Programming ---------------------- https://www.youtube.com/watch?v=pYKGRZwbuzs
--------------------------------------------- O(n^3) T (the substring also takes O(n) T), O(n) S
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not wordDict:
            return False
        dp = [False] * (len(s) + 1)                # Step no.1: 题目要求我们返回一个Boolean，大概率就是DP，并且DP state 也应设为Boolean
                                                   # dp[i] is used for recording the result of length i substring in s
                                                   # IMPORTANT !!!!!! dp = [False] * (len(s) + 1) not dp = [False] * (len(wordDict) + 1)
        dp[0] = True                               # Step no.2
        for i in range(1, len(s) + 1):             # Step no.3: 用i先遍历整个s, Remember i here is the i for dp not the i for s
            for j in range(i - 1, -1, -1):         # 多设置了一个j变量用来从后往前看，如果从后往前看时，在wordDict中，只要前面的状态是True，
                if s[j:i] in wordDict and dp[j]:   # 且此刻的subarray也在wordDict中，此时的状态也是True
                    dp[i] = True
        return dp[-1]                              # Step no.4



Java Version no.1: --------------------------------------- O(n^n)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Set<String> set = new HashSet<>(wordDict);
        return backtracking(s, set, 0);
    }
    
    public boolean backtracking(String s, Set<String> set, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end ++) {
            if (set.contains(s.substring(start, end)) && backtracking(s, set, end)) {
                return true;
            }
        }
        return false;
    }
}


Java Version no.2: ------------------------------------------ O(n^2)
class Solution {
    Map<Integer, Boolean> memo = new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Set<String> set = new HashSet<>(wordDict);
        return backtracking(s, set, 0);
    }
    
    public boolean backtracking(String s, Set<String> set, int start) {
        if (start == s.length()) {
            return true;
        }
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        for (int end = start + 1; end <= s.length(); end ++) {
            if (set.contains(s.substring(start, end)) && backtracking(s, set, end)) {
                memo.put(start, true);
                return true;
            }
        }
        memo.put(start, false);
        return false;
    }
}


Java Version no.3: ------------------------------ O(n^3)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i ++) {
            for (int j = i - 1; j >= 0; j --) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        System.out.println(dp);
        return dp[dp.length - 1];
    }
}