leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

unique-binary-search-treesV2.dart (725B)

      1 //Added memoization which stops me from getting a tle.
      2 //Time: 290ms Beats: 100%
      3 //Memory: 140.1MB Beats: 100%
      4 
      5 class Solution {
      6   int numTrees(int n) {
      7     List<int> val_list = [];
      8     for(int i = 1 ; i <= n ; ++i){
      9         val_list.add(i);
     10     }
     11     return trees(val_list, {});
     12   }
     13 
     14 int trees(List<int> vals, Map<int, int> memo){
     15   if(memo.containsKey(vals.length)){
     16     return (memo[vals.length] ?? 0);
     17   }
     18   if(vals.length == 0){
     19     return 1;
     20   }
     21 
     22   int current_val = 0;
     23   for(int i = 0 ; i < vals.length ; ++i){
     24     List<int> left = vals.sublist(0,i);
     25     List<int> right = vals.sublist(i + 1);
     26     current_val += trees(left, memo) * trees(right,memo);
     27   }
     28   memo[vals.length] = current_val;
     29   return current_val;
     30 }
     31 
     32 }