decode-ways.dart (1178B)
1 //Given a string input s that has only numbers 2 //return the total number of possible ways to decode 3 //the numbers assuming that 1 = A and so on all the way to 4 //26 = z. Given this for *all values in the list there will be 5 //multiple ways to express them by either including the value 6 //before, after, or only the current. To solve this I used recursion 7 //and memoization to remember the already computed permutations for the 8 //last values thus saving on computing those again. Given this the time complexity 9 //of this code is O(n). 10 //Time: 263ms Beats: 83.33% 11 //Memory: 143.5MB Beats: 16.67% 12 13 class Solution { 14 Map<int,int> memo = {}; 15 int numDecodings(String s) { 16 if(memo[s.length] != null){ 17 return (memo[s.length] ?? 0); 18 } 19 if(s.length <= 1){ 20 if(s.length != 0){ 21 if(s[0] == '0'){ 22 return 0; 23 } 24 } 25 return 1; 26 } 27 if(s[0] == '0'){ 28 return 0; 29 } 30 int return_val = 0; 31 return_val += numDecodings(s.substring(1)); 32 String second = s.substring(0,2); 33 if(int.parse(second) <= 26){ 34 return_val += numDecodings(s.substring(2)); 35 } 36 memo[s.length] = return_val; 37 return return_val; 38 } 39 }