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:2Explanation:It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input:"226"Output:3Explanation:It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
很多時(shí)候玖姑，動(dòng)態(tài)規(guī)劃的問(wèn)題其實(shí)不用創(chuàng)建完整的數(shù)組慨菱，所以可以第一遍先new一個(gè)數(shù)組，作對(duì)了之后符喝，再把new去掉闪彼，直接用變量替換需要用到的那幾個(gè)子問(wèn)題解即可
class Solution {
? ? public int numDecodings(String s) {
? ? ? ? int n = s.length();
? ? ? ? int pre1 = 0, pre2 = 0;
? ? ? ? int res = 0;
? ? ? ? int preNum = 0;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? int cur = 0;
? ? ? ? ? ? int curNum = s.charAt(i) - '0';
? ? ? ? ? ? if (curNum >= 1 && curNum <= 9) cur += i >= 1 ? pre1 : 1;
? ? ? ? ? ? int twoNum = 10 * preNum + curNum;
? ? ? ? ? ? if (i >= 1 && twoNum >= 10 && twoNum <= 26) cur += i >= 2 ? pre2 : 1;
? ? ? ? ? ? if (cur == 0) return 0;
? ? ? ? ? ? pre2 = pre1;
? ? ? ? ? ? pre1 = cur;
? ? ? ? ? ? preNum = curNum;
? ? ? ? }
? ? ? ? return pre1;
? ? }
}
