What's time complexity of algorithm for "Word Break"?

Question

Word Break(Dynamic Programming)
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

• s = "catsanddog",dict = ["cat", "cats", "and", "sand", "dog"].
• A solution is ["cats and dog", "cat sand dog"].

---

Question:

• Time complexity = ?
• Space complexity = ?

---

Personally I think,

• Time complexity = O(n!), n is the length of the given string.
• Space complexity = O(n).

Doubt:
Seems if without DP, the time complexity = O(n!), but with DP, what is that?

---

Solution: DFS+Backtracking(Recursion) + DP:
Code: Java

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> list = new ArrayList<String>();

        // Input checking.
        if (s == null || s.length() == 0 || 
            dict == null || dict.size() == 0) return list;

        int len = s.length();

        // memo[i] is recording,
        // whether we cut at index "i", can get one of the result.
        boolean memo[] = new boolean[len];
        for (int i = 0; i < len; i ++) memo[i] = true;

        StringBuilder tmpStrBuilder = new StringBuilder();
        helper(s, 0, tmpStrBuilder, dict, list, memo);

        return list;
    }

    private void helper(String s, int start, StringBuilder tmpStrBuilder,
                        Set<String> dict, List<String> list, boolean[] memo) {

        // Base case.
        if (start >= s.length()) {
            list.add(tmpStrBuilder.toString().trim());
            return;
        }

        int listSizeBeforeRecursion = 0;
        for (int i = start; i < s.length(); i ++) {
            if (memo[i] == false) continue;

            String curr = s.substring(start, i + 1);
            if (!dict.contains(curr)) continue;

            // Have a try.
            tmpStrBuilder.append(curr);
            tmpStrBuilder.append(" ");

            // Do recursion.
            listSizeBeforeRecursion = list.size();
            helper(s, i + 1, tmpStrBuilder, dict, list, memo);

            if (list.size() == listSizeBeforeRecursion) memo[i] = false;

            // Roll back.
            tmpStrBuilder.setLength(tmpStrBuilder.length() - curr.length() - 1);
        }
    }
}

Answer 1

If $n$ is the length of string and $m$ the size of the dictionary, DP will use $O(n)$ space and $O(nm)$ time at most if you want to find just one solution. As you have to list all solutions, the time is exponential in $n$ because of the many possible solutions (think of "$aaaaa\ldots a$" with dictionary "$a$", "$aa$").