91. Decode Ways

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

```'A' -> 1
'B' -> 2
...
'Z' -> 26```

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

```Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).```

Example 2:

```Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).```

```'A' -> 1
'B' -> 2
...
'Z' -> 26```

```f(n) = f(n - 1) + f(n - 2) 当前字符在［1,9] 之间，且当前字符与前一字符组成的数在［11,19]［21,26]之间
f(n) = f(n - 1) 当前字符与前一字符组成的数不在［1,9]［11,26]之间
f(n) = f(n - 2) 当前字符与前一字符组成的数为10或20```

Runtime: 5470 ms, faster than 0.99% of Java online submissions for Decode Ways.

Memory Usage: 50.2 MB, less than 0.97% of Java online submissions for Decode Ways.

```class Solution {
public int numDecodings(String s) {
return numDecodings(s, s.length());
}

// length > 0
private int numDecodings(String s, int length) {
// 字符不为空 初始化length0 为1
if (0 == length) {
return 1;
}
if (1 == length) {
if (Integer.parseInt(s.substring(length - 1, length)) > 0) {
return 1;
}
return 0;
}

int last = length - 1;
int prev = last - 1;
int valLast = Integer.parseInt(s.substring(last, last + 1));
int valPrev = Integer.parseInt(s.substring(prev, prev + 2));
if (10 == valPrev || 20 == valPrev) {
return numDecodings(s, length - 2);
} else if (valPrev >= 10 && valPrev <= 26) {
return numDecodings(s, length - 1) + numDecodings(s, length - 2);
}

if (valLast > 0 && valLast < 10) {
return numDecodings(s, length - 1);
}

return 0;
}
}```

Runtime: 3 ms, faster than 43.60% of Java online submissions for Decode Ways.

Memory Usage: 34.6 MB, less than 3.09% of Java online submissions for Decode Ways.

```class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') {
return 0;
}
int p = 1, q = 1, result = 1;
for (int i = 1; i < s.length(); i++) {
int num1 = s.charAt(i) - '0';
int num2 = Integer.valueOf(s.substring(i - 1, i + 1));
if (num2 == 10 || num2 == 20) {
result = p;
} else if (10 < num2 && num2 <= 26) {
result = p + q;
} else if (num1 > 0 && num1 < 10) {
result = q;
} else {
return 0;
}

p = q;
q = result;
}

return result;
}
}```

上一篇

下一篇

评论已经被关闭。

插入图片

1. 移动互联