|
| 1 | +// Optimal |
| 2 | +classSolution { |
| 3 | + |
| 4 | +publicintnumDecodings(Strings){ |
| 5 | +int[]dp =newint[s.length()+1]; |
| 6 | +inttwoBack =1;// empty string |
| 7 | +intoneBack =s.charAt(0) =='0' ?0:1; |
| 8 | +intcurrent =oneBack; |
| 9 | +for(inti =2;i <s.length()+1;i++){ |
| 10 | +current =0; |
| 11 | +if(s.charAt(i-1) !='0'){ |
| 12 | +current +=oneBack; |
| 13 | + } |
| 14 | +if(s.charAt(i-2) =='1' || (s.charAt(i-2) =='2' &&s.charAt(i-1) <'7')){ |
| 15 | +current +=twoBack; |
| 16 | + } |
| 17 | +twoBack =oneBack; |
| 18 | +oneBack =current; |
| 19 | + } |
| 20 | +returncurrent; |
| 21 | + } |
| 22 | + |
| 23 | +} |
| 24 | + |
| 25 | +//bottom up |
| 26 | +classSolution { |
| 27 | + |
| 28 | +publicintnumDecodings(Strings){ |
| 29 | +int[]dp =newint[s.length()+1]; |
| 30 | +dp[0] =1;// empty string |
| 31 | +dp[1] =s.charAt(0) =='0' ?0:1; |
| 32 | +for(inti =2;i <s.length()+1;i++){ |
| 33 | +if(s.charAt(i-1) !='0'){ |
| 34 | +dp[i] +=dp[i-1]; |
| 35 | + } |
| 36 | +if(s.charAt(i-2) =='1' || (s.charAt(i-2) =='2' &&s.charAt(i-1) <'7')){ |
| 37 | +dp[i] +=dp[i-2]; |
| 38 | + } |
| 39 | + } |
| 40 | +returndp[s.length()]; |
| 41 | + } |
| 42 | +} |
| 43 | + |
| 44 | +//top down with memoization |
| 45 | +classSolution { |
| 46 | + |
| 47 | +publicintnumDecodings(Strings){ |
| 48 | +returnnumDecodings(s,0,newInteger[s.length()]); |
| 49 | + } |
| 50 | + |
| 51 | +privateintnumDecodings(Strings,inti,Integer[]dp){ |
| 52 | +if(i ==s.length())return1; |
| 53 | +if(s.charAt(i) =='0')return0; |
| 54 | +if(dp[i] !=null)returndp[i]; |
| 55 | +intcount =0; |
| 56 | +count +=numDecodings(s,i+1,dp); |
| 57 | +if(i <s.length()-1 && (s.charAt(i) =='1' ||s.charAt(i) =='2' &&s.charAt(i+1) <'7')){ |
| 58 | +count +=numDecodings(s,i+2,dp); |
| 59 | + } |
| 60 | +dp[i] =count; |
| 61 | +returndp[i]; |
| 62 | + } |
| 63 | +} |
| 64 | + |
| 65 | + |