title: What's time complexity of this Algorithm for breaking words? (Dynamic Programming)
body: <blockquote>
    <p><strong>Word Break</strong>(with Dynamic Programming: Top->Down)<br> 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.<br></p>
    
    <p>Return all such possible sentences.<br></p>
    
    <p><strong>For example</strong>, given<br> s = "catsanddog",<br> dict = ["cat", "cats", "and", "sand", "dog"].<br></p>
    
    <p>A solution is ["cats and dog", "cat sand dog"]. <hr>
    <strong>Question:</strong> </p>
    
    <ul>
    <li>Time complexity ?</li>
    <li>Space complexity ?</li>
    </ul>
    
    <p><strong>Personally I think,</strong><br></p>
    
    <ul>
    <li>Time complexity = O(n!), without Dynamic Programming, n is the length    of the given string,</li>
    <li>Space complexity = O(n).</li>
    </ul>
    
    <p><strong>The puzzled:<br></strong></p>
    
    <ul>
    <li>Can not figure out the time complexity with Dynamic Programming. </li>
    <li>It seems that the space complexity above is not correct.</li>
    </ul>
    
    <p><hr>
    <strong>Code</strong>[Java]<br></p>
  </blockquote>
  
  <pre><code>public class Solution {
      public List&lt;String&gt; wordBreak(String s, Set&lt;String&gt; dict) {
          List&lt;String&gt; list = new ArrayList&lt;String&gt;();
  
          // 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 &lt; 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&lt;String&gt; dict, List&lt;String&gt; list, boolean[] memo) {
  
          // Base case.
          if (start &gt;= s.length()) {
              list.add(tmpStrBuilder.toString().trim());
              return;
          }
  
          int listSizeBeforeRecursion = 0;
          for (int i = start; i &lt; 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);
          }
      }
  }
  </code></pre>