title: Converting my recursive function to top down dynamic programming
body: <p>I have been struggling with this problem all week. The problem is as follows, given such a string, S, of n uppercase letters, describe an efficient way of breaking it into a sequence of valid English words. You may assume the valid(s) function runs in O(1) time. Example of how it should work is like this. Lets say you are given <code>CABIN</code> as input. <code>[A, BIN, IN, CAB, CABIN]</code> are valid words. Function should return <code>[[CAB, IN], [CABIN]]</code>.
  <br><br>
  I managed to get a recursive function working but can't seem to figure out how to create a dynamic solution.</p>
  
  <h2>Recursive Implementation (JS)</h2>
  
  <pre><code>var test = 'ABORTTHEPLANMEETATTHEDARKCABIN';
  var words = {
      ABORT: true,
      THE: true,
      PLAN: true,
      MEET: true,
      AT: true,
      DARK: true,
      CABIN: true
  };
  var valid = function(word) {
      if (words[word]) return true;
      return false;
  };
  String.prototype.suffix = function(i) {
      return this.substring(this.length - i);
  };
  
  String.prototype.prefix = function(i) {
      return this.substring(0, i);
  };
  
  
  var breakCode = function(S) {
      var T = [];
  
      for (var i = 1; i &lt;= S.length; i++) {
          var str = S.suffix(i);
          if (valid(str)) {
              if (i &lt; S.length) {
                  var prefix = S.prefix(S.length - i);
                  var P = breakCode(prefix);
                  P.forEach(function(p) {
                      p.push(str);
                      T.push(p);
                  });
              } else {
                  T.push([str]);
              }
          }
      }
      return T;
  }
  </code></pre>
  
  <h2>Non Working Attempt at DP Solution</h2>
  
  <pre><code>var breakCodeDP = function(S) {
      var T=[];
  
      for (var i = 1; i &lt;= S.length; i++) {
          for (var j = 1; j &lt;= i; j++) {
              var str = S.suffix(j);
              if (valid(str)) {
                  if (j &lt; i) {
                      var P = T[i - j];
                      // console.log(T);
                      // P = typeof P === 'undefined'?[]:P;
                      // P.forEach(function(p) {
                      //   if (!Array.isArray(T[i])) T[i] = [];
                      //     T[i].push([p, str]);
                      // });
                  } else {
                      T[i] = [str];
                  }
              }
          }
      }
  }
  </code></pre>