-
Notifications
You must be signed in to change notification settings - Fork 2
/
DecodeWays.java
48 lines (40 loc) · 1 KB
/
DecodeWays.java
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
package com.algorithm.playground.leetcode.problems.lc0.lc90.lc91;
/**
* https://leetcode.com/problems/decode-ways/
* <p>
* A message containing letters from A-Z is being encoded to numbers using the following mapping:
* <p>
* 'A' -> 1
* 'B' -> 2
* ...
* 'Z' -> 26
* Given a non-empty string containing only digits, determine the total number of ways to decode it.
*/
public class DecodeWays {
class Solution {
public int numDecodings(String s) {
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = isValid(s.charAt(0)) ? 1 : 0;
for (int i = 2; i <= s.length(); i++) {
if (isValid(s.charAt(i - 1))) {
dp[i] += dp[i - 1];
}
if (isValid(s.charAt(i - 2), s.charAt(i - 1))) {
dp[i] += dp[i - 2];
}
}
return dp[s.length()];
}
private boolean isValid(char ch) {
return ch != '0';
}
private boolean isValid(char ch1, char ch2) {
if (!isValid(ch1)) {
return false;
}
int val = ((ch1 - '0') * 10) + (ch2 - '0');
return val <= 26;
}
}
}