解碼方法

題目描述：一條包含字母 A-Z 的消息通過以下映射進(jìn)行了 編碼 ：

'A' -> 1?

'B' -> 2?

...?

'Z' -> 26?

要 解碼 已編碼的消息，所有數(shù)字必須基于上述映射的方法，反向映射回字母（可能有多種方法）。例如，"11106" 可以映射為：

"AAJF" ，將消息分組為 (1 1 10 6) "KJF" ，將消息分組為 (11 10 6) 注意，消息不能分組為 ?(1 11 06) ，因?yàn)?"06" 不能映射為 "F" ，這是由于 "6" 和 "06" 在映射中并不等價(jià)。

給你一個(gè)只含數(shù)字的 非空 字符串 s ，請計(jì)算并返回 解碼 方法的 總數(shù) 。

題目數(shù)據(jù)保證答案肯定是一個(gè) 32 位 的整數(shù)。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/decode-ways/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸 窮舉

• 首先，當(dāng)s為null或者是空字符串或者s是以0開頭的字符串，不可能映射成功，直接返回0。

• 如果s的長度為1，直接返回1。

• 然后是遞歸處理當(dāng)s的長度大于1的情況，遞歸方法處理邏輯如下（方法的入?yún)?span id="s0sssss00s" class="md-pair-s " style="">left和right分別為當(dāng)前要匹配的字符的開始和結(jié)束位置0 < (right - left) < 3）：

• 如果left位置的數(shù)字為0即要匹配的字符是以0開頭，則無法映射，直接返回；

• 如果left和right所匹配的字符數(shù)大于26，無法映射，返回；

• 如果right為s的最后一位，則result加1，返回；

• 如果right為s的倒數(shù)第二位，且最后一位不是0，則result加1，返回；

• 后面則根據(jù)right后的位數(shù)繼續(xù)遞歸處理right ~ right + 1和right ~ right + 2的情況。

• 最后返回result即為解碼方法的總數(shù)。

【每日寄語】 與天奮斗，其樂無窮！與地奮斗，其樂無窮！與人奮斗，其樂無窮！