140. Word Break II (backtracking)

Latest:

Time complexity: O(2^n)

The algorithm explores all possible ways to break the string into words. 
In the worst case, where each character can be treated as a word, the recursion tree has 2^n
leaf nodes, resulting in an exponential time complexity.

Space complexity: O(2^n)

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>();
        for (String w : wordDict) {
            wordSet.add(w);
        }
        List<List<String>> result = new ArrayList<>();
        backtracking(0, s, wordSet, new ArrayList<>(), result);

        List<String> res = new ArrayList<>(); 
        for (List<String> list : result) {
            StringBuilder sb = new StringBuilder();
            for (String str : list) {
                sb.append(str).append(" ");
            }
            sb.deleteCharAt(sb.length()-1);
            res.add(sb.toString());
        }
        return res;
    }
    private void backtracking(int start, String s, Set<String> wordSet, List<String> list, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(list));
        }
        for (int i = start; i < s.length(); i++) {
            String substr = s.substring(start, i+1);
            if (wordSet.contains(substr)) {
                list.add(substr);
                backtracking(i+1, s, wordSet, list, result);
                System.out.println(list);
                list.remove(list.size()-1);
            }
        }
    }
}
/***
Time complexity: O(2^n)

The algorithm explores all possible ways to break the string into words. 
In the worst case, where each character can be treated as a word, the recursion tree has 2^n
leaf nodes, resulting in an exponential time complexity.

Space complexity: O(2^n)

catsanddog

i == s.length


    catsand
      /\   
  cat    cats    
    /.    \
  sand    and


  catsand = cat + f(3,xx) = cat + sand
          = cats + f(4, xx) = cats + and

start dfs on i index(0 1 2 is cat), pass dfs(i+1) = dfs(3)  to next dfs
[cat, sand, dog] -> execute dfs() to end
list.remove(list.size()-1); // bactracking
[cat, sand]
list.remove(list.size()-1);
[cat]
list.remove(list.size()-1);
[]

backtrack to original i index(3), start to run again.. 
then find cats (index = 0 1 2 3) is ok, so pass dfs(i+1) = dfs(4)  to next dfs
[cats, and, dog] -> execute dfs() to end
list.remove(list.size()-1);
[cats, and]
list.remove(list.size()-1);
[cats]      
list.remove(list.size()-1);
[]
 */

O(2^N * MN)

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        dfs(s, wordDict, 0, new ArrayList<>(), result);
        return result;
    }
    private void dfs(String s, List<String> wordDict, int start, List<String> track, List<String> result) {
        if (start == s.length()) {
            result.add(String.join(" ", track));
            return;
        }
        for (String w : wordDict) {
            int len = w.length();
            if (start + len > s.length()) {
                continue;
            }
            String prefix = s.substring(start, start + len);
            if (w.equals(prefix)) {
                track.add(w);
                dfs(s, wordDict, start + len, track, result);
                track.remove(track.size()-1);
            }
        }
    }
}

/*
catsanddog

wordDict = ["cat","cats","and","sand","dog"]

["cats and dog","cat sand dog"]

loop
wordDict = ["cat","cats","and","sand","dog"]

try to find the prefix in this s catsanddog

cat

cat sanddog
---

prefix: cat into a list -> choose to add list 

2. hanlder remain string
sanddog

in same way -> so dfs()


3. backtracking
cancel this add list


prefix: cats into a list -> choose to add list 
cats anddog

remain string -> anddog

at last find all words can compose the string s

base case: s.length() == start (start index is used to find prefix)
start build a string with space "cats and dog", and add to result
*/

use dfs + memo

time compexity is O(n^4... almost like backtracking

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, 0, new HashSet<>(wordDict), new ArrayList[s.length()]);
    }
    private List<String> dfs(String s, int start, Set<String> dict, List<String>[] memo) {
        List<String> result = new ArrayList<>();
        if (s.length() == start) {
            result.add("");
            return result;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (dict.contains(sub)) {
                List<String> list = dfs(s, i, dict, memo);
                for (String next : list) {
                    if (next.isEmpty()) {
                        result.add(sub);
                    } else {
                        result.add(sub + " " + next);
                    }
                }
            }
        }
        return memo[start] = result;
    }
}