139. Word Break

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

Solution:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // leet code
        // i 
        // substring  (i, j ) wordDict -> true

        int n = s.length();
        Map<Integer, Integer> map = new HashMap<>();

        boolean[] dp = new boolean[n];

        // dp[i][j] means -> exit in the wordDict

        Trie trie = new Trie();
        for (String w : wordDict){
            trie.insert(w);
        }


        for (int i = 0; i < n; i++){
            if (i == 0 || dp[i - 1] == true){
                TrieNode node = trie.root;
                for (int j = i; j < n; j++){
                    char ele = s.charAt(j);
                    if (!node.children.containsKey(ele)){
                        break;
                    }

                    node = node.children.get(ele);
                    if (node.isWord){
                        dp[j] = true;
                    }
                }
            }


        }

        return dp[n - 1];


    }

    class TrieNode{
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
    } 


    class Trie{
        public TrieNode root;

        Trie(){
            root = new TrieNode();
        }

        public void insert(String word){
            TrieNode cur = root;
            for (char ch : word.toCharArray()){
                if (cur.children.containsKey(ch)){
                    cur = cur.children.get(ch);
                }else{
                    cur.children.put(ch, new TrieNode());
                    cur = cur.children.get(ch);
                }
            }
            cur.isWord = true;
        }

        public boolean isPrefix(String word){
            TrieNode cur = root;
            for (char ch : word.toCharArray()){
                if (!cur.children.containsKey(ch)){
                    return false;
                }
            }
            return true;
        }

        public boolean isWord(String word){
            TrieNode cur = root;
            for (char ch : word.toCharArray()){
                if (!cur.children.containsKey(ch)){
                    return false;
                }
            }
            return cur.isWord;
        }
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       // Assume input is not ""
       // M[i] represents the substring[0, i);
       // M[0] represents "" , M[1] represent s[0]; M[2] represent s[0-2]
       boolean[] M = new boolean[s.length() + 1];
       // That's why we need +1 here
       M[0] = true;
       // 0 represent ""
       for (int i = 1; i <= s.length(); i++){
           // i letter // linear scan 回头看
           for (int j = 0; j < i; j++){
               // first j letter as 左大段 // 这个for loop 在切
               if (M[j] && wordDict.contains(s.substring(j, i))){
                // cut left    && cut right
                // substring begins at index i and extends to index i-1
                   M[i] = true;
                   break;
               }

           }
       }
       return M[s.length()];

    }
}
// time =  O(n^3) because of the string.substring API and the hashset.contains API.
// Space = O(n) or O(n^3) if you cannot assume GC happens immediatel

// Off by 1
// M[i] 里的i 代表的含义不是index, 代表的是长度
// M[i] 长度为i的string 能不能被切分开每一段都在dict里

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        // dp[i] means from s [0, s) whether is word in the wordDict
        // dp[0] ""

        dp[0] = true; // ""


        for (int i = 1; i < s.length() + 1; i++){
            for (int j = 0; j < i; j++){
                if (dp[j] == true && wordDict.contains(s.substring(j, i))){
                    dp[i] = true; 
                    break;
                }
            }
        }

        return dp[s.length()];


    }
}

/*
    leetcode 
   TFFFT
       j
 */

 // TC: O(n^2)
 // SC: O(n)