問題描述
給定一個數(shù)字圆兵，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”枢贿，……殉农，11 翻譯成 “l(fā)”，……局荚，25 翻譯成 “z”超凳。一個數(shù)字可能有多個翻譯愈污。請編程實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法轮傍。
示例 1:
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯暂雹，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"提示：
0 <= num < 231
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)创夜，非商業(yè)轉(zhuǎn)載請注明出處杭跪。
解決辦法
從左往右遞歸+備忘錄
利用遞歸從左到右尋求結(jié)果。
class Solution {
HashMap<String,Integer> map = new HashMap<>();
public int translateNum(int num){
return translateNumStr(num+"");
}
public int translateNumStr(String numStr) {
//輔助空間用來避免重復(fù)的計算
if(map.containsKey(numStr))
return map.get(numStr);
//遞歸的結(jié)尾
if(numStr.length()<=1)
return 1;
int preTwo = Integer.parseInt(numStr.substring(0,2));
int result = 0;
if(preTwo<=25&&preTwo>=10){
result = translateNumStr(numStr.substring(1))+translateNumStr(numStr.substring(2));
map.put(numStr,result);
return result;
}else{
result = translateNumStr(numStr.substring(1));
map.put(numStr,result);
return result;
}
}
}
image.png
從右往左遞歸
從左往右判斷驰吓，拿到數(shù)字的前兩位很麻煩涧尿，需要轉(zhuǎn)換成string，如果是從右往左前進的話棚瘟，那么就會容易很多现斋。
class Solution {
public int translateNum(int num) {
if(num<10)
return 1;
if(num%100<=25&&num%100>=10){
return translateNum(num/10)+translateNum(num/100);
}else{
return translateNum(num/10);
}
}
}
image.png
