091. Decode Ways

  • 19.6%

https://leetcode.com/problems/decode-ways/

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.


方法一:

两个两个的解决,一个一个的遍历,两个两个的验证,防止100这样的无法解析的。

对于数字,有两种解码方式。

一种是s[i-2] + ‘i-1, i’(i-1,i组合成一个字母),一种是s[i-1] + ‘i’ (i自己组合成一个方式)

首先,如果s[i] == ‘0’这种情况下,s[i-1]解码失效,设定值为0

然后’i-1,i’组合成一个字母的话, 就可以更新s[i]解码方式为s[i-1]和s[i-2]的和了

如果组合不成字母,则s[i] = s[i-1]

0ms, 73.36%, September 20, 2016

https://discuss.leetcode.com/topic/7025/a-concise-dp-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int numDecodings(string s) {
if(!s.size() || s.front() == '0') return 0;
// r2: decode ways of s[i-2] , r1: decode ways of s[i-1]
int r1 = 1, r2 = 1;
for(int i=1; i<s.size(); i++){
// zero voids ways of the last because zero cannot be used separately
if(s[i] == '0') r1 = 0;
// possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
if(s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6'){
r1 = r1 + r2;
r2 = r1 - r2;
}
// one-digit letter, no new way added
else
r2 = r1;
}
return r1;
}
};

我的代码实现:

两个变量,r1, r2,一个是遍历到i时,r1表示,从开始至i-2位时的decode ways

r2表示开始至i-1的decode ways

更新时,新的r1显然是等于r2。 新的r2,要从r1和r2及他们后面一两位的情况,是否合法去判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numDecodings(string s) {
// string的函数front()
if(s.empty() || s.front()=='0')
return 0;
int r1=1, r2=1;
for(int i=1; i<s.size(); i++){
int nr2 = 0;
if(s[i]!='0')
nr2 += r2;
if(s[i-1]=='1' || s[i-1]=='2'&&s[i]<='6')
nr2 += r1;
r1 = r2;
r2 = nr2;
}
return r2;
}
};

我的代码实现二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(n<1) return 0;
// r1 i-2, r2 i-1
int r1 = 1, r2 = s[0]>='1' && s[1]<='9' ? 1 : 0;
for(int i=1; i<n; i++){
int nr1 = r2;
int nr2 = 0;
if(s[i]>='1' && s[i]<='9')
nr2 += r2;
if(s[i-1]=='1' || s[i-1]=='2' && s[i]<='6')
nr2 += r1;
r1 = nr1;
r2 = nr2;
}
return r2;
}
};

方法二:

https://discuss.leetcode.com/topic/15440/my-c-0ms-dp-solution-o-n

My c++ 0ms DP solution O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n = s.size();
if(n == 0 || s[0] == '0') return 0;
if(n == 1) return 1;
int res = 0,fn_1 = 1,fn_2 = 1;
for(int i = 1;i < n;i++){
int temp = fn_1;
if(isValid(s[i])&&isValid(s[i-1],s[i])) res+=fn_1+fn_2;
if(!isValid(s[i])&&isValid(s[i-1],s[i])) res+=fn_2;
if(isValid(s[i])&&!isValid(s[i-1],s[i])) res+=fn_1;
if(!isValid(s[i])&&!isValid(s[i-1],s[i])) return 0;
fn_1 = res;
fn_2 = temp;
res = 0;
}
return fn_1;
}
bool isValid(char a,char b){
return a == '1'||(a == '2' && b <='6');
}
bool isValid(char a){
return a != '0';
}

python

62ms, 23.31%, September 20, 2016

https://discuss.leetcode.com/topic/19042/1-liner-o-1-space

w tells the number of ways

v tells the previous number of ways

d is the current digit

p is the previous digit

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
v, w, p = 0, int(s>''), ''
for d in s:
v, w, p = w, (d>'0')*w + (9<int(p+d)<27)*v, d
return w
1
2
def numDecodings(self, s):
return reduce(lambda(v,w,p),d:(w,(d>'0')*w+(9<int(p+d)<27)*v,d),s,(0,s>'',''))[1]*1

java

5ms, 27.87%, September 20, 2016

https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation

I used a dp array of size n + 1 to save subproblem solutions. dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1: 0;
for(int i = 2; i<=n; i++){
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first >= 1 && first <= 9)
dp[i] += dp[i-1];
if(second >= 10 && second <= 26)
dp[i] += dp[i-2];
}
return dp[n];
}
}

https://discuss.leetcode.com/topic/2562/dp-solution-java-for-reference

DP Solution (Java) for reference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;

int[] memo = new int[n+1];
memo[n] = 1;
memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

for (int i = n - 2; i >= 0; i--)
if (s.charAt(i) == '0') continue;
else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

return memo[0];
}
}
谢谢你,可爱的朋友。