首页 > 代码库 > Decode Ways

Decode Ways

2024-10-27 16:48:39   208人阅读

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

这道题有点像https://oj.leetcode.com/problems/climbing-stairs/爬梯子那道题，我在那道题的基础上用DP的思路，修修改改。写的略挫，一会儿去看看别人怎么A的

 1 public class Solution { 2     public int numDecodings(String s) { 3         if(0 == s.length() || s.charAt(0) == ‘0‘) 4             return 0; 5         int ways[] = new int[s.length() + 1]; 6         for(int i = 0; i <= s.length(); i++){ 7             if(i == 1 || i == 0){ 8                 ways[i] = 1; 9             }10             else{11                 if(i < s.length() && s.charAt(i) == ‘0‘)12                 {13                     ways[i] = ways[i - 1];14                     continue;15                 }16                 String subStr = s.substring(i - 2, i);17                 int num = Integer.valueOf(subStr);18                 if(num == 0)19                     return 0;20                 if(num > 26 && num % 10 == 0)21                     return 0;22                 else if(num <= 26 && s.charAt(i - 1) != ‘0‘ && s.charAt(i - 2) != ‘0‘)23                     ways[i] = ways[i - 1] + ways[i - 2];24                 else25                     ways[i] = ways[i - 1];                26             }//else27         }//for28         29         return ways[s.length()];30     }31 }

 

Decode Ways


联系
我们