什么时候该算法破字的复杂性？ （动态规划）

本文介绍了什么时候该算法破字的复杂性？ （动态规划）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述   

字歇（用动态规划：上>下）给定一个字符串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