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
Given encoded message
"12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding
Code (Java):"12"
is 2.public class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } int[] dp = new int[s.length()]; if (s.charAt(0) >= '1' && s.charAt(0) <= '9') { dp[0] = 1; } else { return 0; } if (s.length() <= 1) { return 1; } // Initialize dp[1] if (s.charAt(1) >= '1' && s.charAt(1) <= '9') { dp[1] = 1; } if (isValid(s.substring(0, 2))) { dp[1] += 1; } for (int i = 2; i < s.length(); i++) { if (s.charAt(i) >= '1' && s.charAt(i) <= '9') { dp[i] = dp[i - 1]; } if (isValid(s.substring(i - 1, i + 1))) { dp[i] += dp[i - 2]; } } return dp[s.length() - 1]; } private boolean isValid(String str) { if (str.charAt(0) == 0) { return false; } int val = Integer.valueOf(str); if (val >= 10 && val <= 26) { return true; } else { return false; } } }
Update on 2/8/16:
public class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } if (s.charAt(0) == '0') { return 0; } int[] dp = new int[s.length() + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= s.length(); i++) { if (s.charAt(i - 1) != '0') { dp[i] = dp[i - 1]; } if (isValid(s.substring(i - 2, i))) { dp[i] += dp[i - 2]; } } return dp[s.length()]; } private boolean isValid(String s) { if (s.charAt(0) == '0') { return false; } int num = Integer.parseInt(s); if (num >= 1 && num <= 26) { return true; } return false; } }
No comments:
Post a Comment