fishercoderLeetcode/MEDIUM/src/medium/DecodeWays.java at master · fighter3228/fishercoderLeetcode · 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package medium;
import  java.util.*;
/**
 * Created by fishercoder1534 on 10/3/16.
 */
public class DecodeWays {
    /**Then I found this post is very concise: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation*/
    public static int numDecodings_solution2(String s) {
        if(s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = (s.charAt(0) != '0') ? 1 : 0;
        for(int i = 2; i <= s.length(); i++){
            int first = Integer.valueOf(s.substring(i-1,i));
            int second = Integer.valueOf(s.substring(i-2, i));
            if(first > 0 && first <= 9) dp[i] += dp[i-1];
            if(second >= 10 && second <= 26) dp[i] += dp[i-2];
        }
        return dp[s.length()];
    }


    /**My original accepted yet lengthy solution.*/
    public static int numDecodings_solution1(String s) {

        if(s == null || s.length() == 0) return 0;
        Set<String> validStrings = new HashSet();
        validStrings.add("1");
        validStrings.add("2");
        validStrings.add("3");
        validStrings.add("4");
        validStrings.add("5");
        validStrings.add("6");
        validStrings.add("7");
        validStrings.add("8");
        validStrings.add("9");
        validStrings.add("10");
        validStrings.add("11");
        validStrings.add("12");
        validStrings.add("13");
        validStrings.add("14");
        validStrings.add("15");
        validStrings.add("16");
        validStrings.add("17");
        validStrings.add("18");
        validStrings.add("19");
        validStrings.add("20");
        validStrings.add("21");
        validStrings.add("22");
        validStrings.add("23");
        validStrings.add("24");
        validStrings.add("25");
        validStrings.add("26");

        int n = s.length();
        int[] dp = new int[n];
        if(validStrings.contains(s.substring(0,1))) dp[0] = 1;
        else dp[0] = 0;

        for(int i = 1; i < n; i++){
            if(validStrings.contains(s.substring(i,i+1)) && validStrings.contains(s.substring(i-1,i+1))) {
                if(i > 1){
                    dp[i] = dp[i-2] + dp[i-1];
                } else {
                    dp[1] = 2;
                }
            } else if(!validStrings.contains(s.substring(i,i+1)) && !validStrings.contains(s.substring(i-1,i+1))){
                return 0;
            } else if(!validStrings.contains(s.substring(i,i+1)) && validStrings.contains(s.substring(i-1,i+1))){
                if(i > 1) dp[i] = dp[i-2];
                else dp[i] = dp[i-1];
            }
            else dp[i] = dp[i-1];
        }

        return dp[n-1];

    }

    public static void main(String...args){
        String msg = "100";

    }
}