Orange-Bloom/Ways To Decode.java at master · aky91/Orange-Bloom · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//https://www.interviewbit.com/problems/ways-to-decode/

public class Solution {
    public int numDecodings(String A) {

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int ans = solve(0, A, map);

        return ans;
    }

    public int solve(int buff, String A, HashMap<Integer, Integer> map){

        int N = A.length();

        int size = N - buff;

        if(size == 0 || buff == N)
            return 1;

        if(buff > N)
            return 0;

        int ans = 0;

        //1 no.
        if(buff+0 < N){

            int num = A.charAt(buff + 0) - '0';

            if(num >= 1 && num <= 9){

                if(map.containsKey(buff+1))
                    ans += map.get(buff+1);
                else{
                    int temp = solve(buff+1, A, map);

                    if(temp != -1)
                        ans +=  temp;
                }
            }
        }

        //2 no.
        if(buff+0 < N && buff+1 < N){

            int num = (A.charAt(0 + buff) - '0')*10 + (A.charAt(1 + buff) - '0');

            if(num >= 10 && num <= 26){

                if(map.containsKey(buff+2))
                    ans += map.get(buff+2);
                else
                    ans += solve(buff+2, A, map);
            }
        }

        map.put(buff, ans);
        return ans;
    }
}