LeetCode--91. Decode Ways

本文主要是介绍LeetCode--91. Decode Ways，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题链接：https://leetcode.com/problems/decode-ways/

这个问题在剑指Offer中也有类似问题，需要注意的是‘0’和类似以‘012’这类以‘0’开头的串是无法编码的。使用的是经典的DP算法思想，而分析方法是采用自顶向下的递归方法。状态转移方程：

                                                             dp[i]=dp[i+1]+canDeocde(i,i+1)*dp[i+2]

这里需要小心的初始状态：dp[0]和dp[1]

dp[n-1]=s.charAt(n-1)=='0'?0:1;if(n==1)return dp[0];if(s.charAt(n-2)=='0')dp[n-2]=0;elsedp[n-2]=canDecode(s,n-2)+dp[n-1];

代码如下：

class Solution {public int numDecodings(String s) {int n=s.length();int[] dp=new int[n];dp[n-1]=s.charAt(n-1)=='0'?0:1;if(n==1)return dp[0];if(s.charAt(n-2)=='0')dp[n-2]=0;elsedp[n-2]=canDecode(s,n-2)+dp[n-1];for(int i=n-3;i>=0;i--){if(s.charAt(i)=='0')dp[i]=0;elsedp[i]=dp[i+1]+canDecode(s,i)*dp[i+2];}return dp[0];}public static int canDecode(String s,int i){int tmp=(s.charAt(i)-'0')*10+s.charAt(i+1)-'0';return (tmp>=10 && tmp<=26)?1:0;}
}

 

这篇关于LeetCode--91. Decode Ways的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---