What's time complexity of this Algorithm for b

问题:

Word Break(with Dynamic Programming: Top->Down)
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!), without Dynamic Programming, n is the length of the given string,
• Space complexity = O(n).

The puzzled:

• Can not figure out the time complexity with Dynamic Programming.
• It seems that the space complexity above is not correct.

---

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);
        }
    }
}

回答1:

With DP:

Time: O(N*M) N - string size M - dict size

Memory: O(N)

See my answer here, with code example:

Dynamic Programming - Word Break

回答2:

It is dynamic problem.

You can maintain two things.

1 DP[i] means when the string is in ith character, there is dp[i] ways to cut it.

2 vector < int> pre[i] means the previous position can reach the current ith position.(It's size must be DP[i])

Time is O(n*m)

Firstly, i is in [0,n):

then find j in [0,i): that substring(j+1,i) is valid.

The validation can be calculated previously. So the time is O(n*m), and you can use vector < int> pre[i] to get all the cutting solution you want.