leetcode

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

target-sumV2.dart (917B)

      1 //This is the same as the other implementation but uses
      2 //memoization and DP to increase the speed greatly.
      3 //Time: 784ms Beats: 100%
      4 //Memory: 175.9MB Beats: 30%
      5 
      6 class Solution {
      7   Map<String,int> vals = {};
      8   int findTargetSumWays(List<int> nums, int target) {
      9       if(vals[nums.length.toString() + " " + target.toString()] != null){
     10           return((vals[nums.length.toString() + " " + target.toString()] ?? 0));
     11       }
     12       if(nums.length == 0){
     13           if(target == 0){
     14               return 1;
     15           }
     16           return 0;
     17       }
     18       int first_val = nums[0];
     19       nums.removeAt(0);
     20       int positive_val = findTargetSumWays( List.from(nums) , target - first_val);
     21       int negative_val = findTargetSumWays( List.from(nums) , target + first_val );
     22       vals[(nums.length + 1).toString() + " " + target.toString()] = positive_val + negative_val; 
     23       return positive_val + negative_val;;
     24 
     25   }
     26 }