2014年4月20日 星期日

[LeetCode] Decode Ways

Problem:
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.
Solution:O(n)
public class Solution {
   public int numDecodings(String s) {
      if(s == null || s.length() == 0 || s.startsWith("0"))
         return 0;
      if(s.length()== 1)
         return 1;
 
      int ways[] = new int[s.length()+1];
      ways[1] = 1;
      ways[0] = 1;
      for(int i=1; i<s.length();i++){
         if(s.charAt(i) != '0'){
     ways[i+1] = ways[i];
  }
  
  String l2 = s.substring(i-1, i+1);
  int num = Integer.parseInt(l2);
  if(num>=10 && num<=26){
     ways[i+1]+= ways[i-1];
         }
      }
      return ways[ways.length-1];
   }   
}  
Key Concept: DP and care about 10~26

沒有留言:

張貼留言