Thinking process - Word Break I

dp[i] is whether the substring from 0 to i can be constructed from the given dictionary

API Methods

ArrayList supports contains

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

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

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

Word Break II

Thinking process I - TLE

There is no duplicates in the dictionary, but I can use one word multiple times.

Time Complexity

n!

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();

        dfsHelper(result, s, wordDict, 0, new StringBuilder());

        return result;
    }

    private void dfsHelper(List<String> result, String s, List<String> wordDict, int start, StringBuilder sb) {
        if (start >= s.length()) {
            result.add(sb.toString().trim());
        }

        for (int i = start + 1; i <= s.length(); ++i) {
            if (wordDict.contains(s.substring(start, i))) {
                sb.append(" ");
                sb.append(s.substring(start, i));
                dfsHelper(result, s, wordDict, i, sb);
                sb.delete(sb.length() - (i - start) - 1, sb.length());
            }
        }
    }
}

Thinking process II - TLE

avoid repeatedly calculate the result of substring

space - time complexity trade - off

Time Complexity

n!

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<String>> map = new HashMap<>();
        List<String> currSubString = new ArrayList<>();
        currSubString.add("");
        map.put(s.length(), currSubString);

        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = i + 1; j <= s.length(); ++j) {
                if (wordDict.contains(s.substring(i, j)) && map.containsKey(j)) {
                    if (!map.containsKey(i)) {
                        map.put(i, new ArrayList<>());
                    }

                    currSubString = map.get(i);
                    for (String str : map.get(j)) {
                        String tmpStr = s.substring(i, j) + " " + str;
                        currSubString.add(tmpStr.trim());
                    }
                }
            }
        }

        return map.containsKey(0) ? map.get(0) : new ArrayList<>();
    }
}

Thinking process

https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs/2

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfsHelper(s, wordDict, new HashMap<String, List<String>>());
    }

    public List<String> dfsHelper(String s, List<String> wordDict, HashMap<String, List<String>> map) {
        if (map.containsKey(s)) 
            return map.get(s);

        List<String>res = new LinkedList<String>();     
        if (s.length() == 0) {
            res.add("");
            return res;
        }

        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> sublist = dfsHelper(s.substring(word.length()), wordDict, map);
                for (String sub : sublist) 
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);               
            }
        }       
        map.put(s, res);
        return res;
    }
}