Use hashable types as hashtable keys
An important requirement of hashtables is that they keys must be hashable:
- has a
.hashCode implementation that returns the same value for two objects that are equal - has a
.equals implementation that returns true for two objects that are equal
Looking at the documentation of MapEntry, it looks like it inherits the hashCode and equals implementations from Object, which means it's not hashable.
The problem is that these objects are not equal:
MapEntry x = MapEntry(a, b); MapEntry y = MapEntry(a, b);
This breaks the caching mechanism of the code, everything is recomputed.
You could implement a Pair with suitable hashCode and equals:
class Pair { final int first, second; Pair(this.first, this.second); bool operator==(Object other) => other is Pair && first == other.first && second == other.second; int get hashCode => Object.hash(first, second); }
Alternatively, you could compute a key to use with the cache, given the range of inputs in the problem description:
class Solution { int findTargetSumWays(List<int> nums, int target) { Map<int, int> dp = {}; int calculate(int i, int sum) { if (i == nums.length) { return sum == target ? 1 : 0; } final k = key(i, sum); return dp[k] ?? (dp[k] = calculate(i + 1, sum + nums[i]) + calculate(i + 1, sum - nums[i])); } return calculate(0, 0); } int key(int index, int sum) { return sum * 1001 + index; } }
Using this key function saves the overhead of object creation.
Programming challenge sites are not benchmarking tools
These sites are not proper benchmarking tools, and there are far too many unknowns an outsider simply cannot know:
- how efficiently are the program executors implemented for each language
- do the programs run on the same hardware
- do the programs run on the same network (same latency)
To name just a few. Don't read too much meaning into the timing results on these sites. They are just good enough to decide if your solution has the target time and space complexity.
Improve the Python code
There are many redundant parentheses:
if(i == len(nums)): return 1 if (total == target) else 0 if((i, total) in dp): return dp[(i, total)]
These could be:
if i == len(nums): return 1 if (total == target) else 0 if (i, total) in dp: return dp[i, total]
You can also take advantage that False is 0 in integer context, and True is 1, simplifying the first conditional:
if i == len(nums): return total == target
Lastly, instead of using dict as the cache, you can benefit from @cache in functools (implicitly imported on leetcode).
Putting it together:
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: @cache def calculate(i, total): if i == len(nums): return total == target return calculate(i+1, total + nums[i]) + calculate(i+1, total - nums[i]) return calculate(0, 0)
