字歇（用动态规划：上>下）给定一个字符串s和文字的字典dict，以s加空格来构造一个句子   其中每个字是一个有效的字典中的单词。

     

返回所有这些可能的句子。

     

例如，因为 S =catsanddog，字典=猫，猫，和，沙，狗。

     

一个解决方案是[猫与狗，猫沙狗。   问：

        在时间复杂度？   在空间的复杂性？         

我个人认为，

        在时间复杂度= O（N！），没有动态规划，n是给定字符串的长度，   空间复杂度= O（N）。         

的疑惑：

        想不通与动态规划的时间复杂度。   在它看来，上方的空间复杂度是不正确的。         

   code 【JAVA]

 公共类解决方案{
    公开名单＆LT;字符串＆GT; wordBreak（字符串S，集＆LT;字符串＆GT;字典）{
        名单＆LT;字符串＆GT;名单=新的ArrayList＆LT;字符串＆GT;（）;

        //输入检查。
        如果（S == NULL || s.length（）== 0 ||
            字典== NULL || dict.size（）== 0）返回目录;

        INT的len = s.length（）;

        //备忘录[i]的记录，
        //我们是否切断指数我，就可以得到结果之一。
        布尔备忘录[] =新的布尔[LEN]
        的for（int i = 0; I＆LT; LEN;我++）备注[I] = TRUE;

        StringBuilder的tmpStrBuilder =新的StringBuilder（）;
        助手（S，0，tmpStrBuilder，字典，列表，备忘录）;

        返回列表;
    }

    私人无效帮手（的String，诠释开始，StringBuilder的tmpStrBuilder，
                        设置＆LT;字符串＆GT;字典，列表和LT;字符串＆GT;列表中，布尔[]备忘录）{

        //基本情况。
        如果（开始＆gt; = s.length（））{
            list.add（tmpStrBuilder.toString（）修剪（））;
            返回;
        }

        INT listSizeBeforeRecursion = 0;
        的for（int i =启动; I＆LT; s.length（）;我++）{
            如果（备注[I] ==假）继续;

            字符串CURR = s.substring（启动，I + 1）;
            如果继续（dict.contains（CURR）！）;

            //有一个尝试。
            tmpStrBuilder.append（CURR）;
            tmpStrBuilder.append（）;

            //做递归。
            listSizeBeforeRecursion =则为list.size（）;
            助手（S，I + 1，tmpStrBuilder，字典，列表，备忘录）;

            如果（则为list.size（）== listSizeBeforeRecursion）备注[I] = FALSE;

            //回滚。
            tmpStrBuilder.setLength（tmpStrBuilder.length（） -  curr.length（） -  1）;
        }
    }
}
 

解决方案

通过DP：

时间：O（N * M）  N - 字符串大小  米 - 字典大小

内存：O（N）

请参阅我的答案在这里，用code例如：

Dynamic编程 - 字歇

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

解决方案

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