Data-Structures---Algorithms/Count Encodings using DP in java at main · uditbhaskar21/Data-Structures---Algorithms · 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
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int dp[] = new  int[str.length()];
        dp[0]=1;
        for (int i=1;i< dp.length;i++){
            if (str.charAt(i-1)=='0' && str.charAt(i)=='0'){
                dp[i]=0;
            }
            else if (str.charAt(i-1)=='0' && str.charAt(i)!='0'){
                dp[i]=dp[i-1];
            }
            else if (str.charAt(i-1)!='0' && str.charAt(i)=='0'){
                if (str.charAt(i-1)=='1' || str.charAt(i) =='2'){
                    dp[i]=(i>=2 ? dp[i-2]:1);
                }else {
                    dp[i]=0;
                }
            }
            else
            {
                if (Integer.parseInt(str.substring(i-1,i+1))<=26){
                    dp[i]=dp[i-1]+(i>=2 ?dp[i-2]:1);
                }else {
                    dp[i]=dp[i-1];
                }
            }
        }
        System.out.println(dp[str.length()-1]);

    }
}