A message containing letters from
A-Z
is being encoded to numbers using the following mapping:'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
Given encoded message
"12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding
"12"
is 2.
Solution:O(n)
public class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0 || s.startsWith("0"))
return 0;
if(s.length()== 1)
return 1;
int ways[] = new int[s.length()+1];
ways[1] = 1;
ways[0] = 1;
for(int i=1; i<s.length();i++){
if(s.charAt(i) != '0'){
ways[i+1] = ways[i];
}
String l2 = s.substring(i-1, i+1);
int num = Integer.parseInt(l2);
if(num>=10 && num<=26){
ways[i+1]+= ways[i-1];
}
}
return ways[ways.length-1];
}
}
Key Concept: DP and care about 10~26
沒有留言:
張貼留言