问题描述
https://leetcode.com/problems/decode-ways/
代码
class Solution {
public int numDecodings(String s) {
//corner case
if(s == null || s.length() == 0) return 0;
int size = s.length();
//when s is 0
if(s.charAt(0) == '0') return 0;
int curWays = 1;
int preWays = 1;
for(int idx = 1; idx < size; idx++){
int tmp = curWays;
if(s.charAt(idx) == '0'){
//if char is 0, it will conbine with the last char. so decode ways equal to last char.
curWays = preWays;
//if char is 0, and it will exceed the range of 0 ~ 26
if(s.charAt(idx - 1) >= '3' || s.charAt(idx - 1) == '0') return 0;
}else{
//if the char between 1 ~ 26
if(s.charAt(idx - 1) != '0' && Integer.valueOf(s.substring(idx - 1, idx + 1)) <= 26){
curWays += preWays;
}else if(s.charAt(idx - 1) == 0){
curWays = curWays;
}
}
//update preWays, which equals last curWays
preWays = tmp;
}
return curWays;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
