91. Decode Ways

这道题和普通的DP题不太一样,用的是top-down的方法。
也就是从n开始,而不是从0开始建表。
注意dp[ ]的size,比string s多1。
base case :dp[n] = 1; dp[n-1] = 0 or 1;
时间O(n),空间也是O(n);

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length()==0)  return 0;
        int n = s.length();
        
        int dp[] = new int[n+1];
        dp[n] = 1;
        dp[n-1] = s.charAt(n-1)=='0'? 0:1;
        
        for(int i=n-2; i>=0; i--) {
            if(s.charAt(i) != '0')
                dp[i] = (Integer.parseInt(s.substring(i,i+2)) <= 26) ? dp[i+1] + dp[i+2] : dp[i+1];
        }
        return dp[0];
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • A message containing letters from A-Z is being encoded to...
    Jeanz阅读 402评论 0 0
  • A message containing letters from A-Z is being encoded to...
    ShutLove阅读 424评论 0 0
  • 在我眼里,企业组织是由人构成的。既然有“指数型企业”,有“独角兽”企业,就一定有“指数型成长人才”和“独角兽”人才...
    马唐阅读 128评论 0 0
  • 明天考毛概,其实这不是个大事,毕竟我们学校是开卷,大后天考教育学才是重头戏,闭卷,而且一学期没听过课,而且老师看着...
    朴菘菘麻麻阅读 263评论 0 0