A message containing the letters A-Z is encoded with the following mapping:
Input: s = "12"Output: 2Explanation: It can be decoded as "AB" (1 2) or "L" (12).
Input: s = "226"Output: 3Explanation: It can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Input: s = "0"Output: 0Explanation: No character maps to a number starting with 0. Valid mappings containing 0 are 'J' -> "10" and 'T'-> "20" . Since there are no characters, there is no efficient way to decode this, as all numbers need to be mapped. Tip:
1 <= s.length <= 100s contain only digits and may contain leading zeros. Method 1: Dynamic Programming (Java) For a given string s, let its length be n, and the characters in it from left to right are s[1],s [2],...,s[n]. We can use dynamic programming to calculate the number of decoding methods for a string. Specifically, let fi represent the number of decoding methods of the first i characters s[1..i] of the string s. When performing state transfer, we can consider which characters in s were used for the last decoding
class Solution { public int numDecodings(String s) { int n = s.length(); int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { if (s.charAt(i - 1) != '0') { f[i] += f[i - 1]; } if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) { f[i] += f[i - 2]; } } return f[n]; } }
func numDecodings(s string) int { n := len(s) // a = f[i-2], b = f[i-1], c = f[i] a, b, c := 0, 1, 0 for i := 1; i <= n; i++ { c = 0 if s[i-1] != '0' { c += b } if i > 1 && s[i-2] != '0' && ((s[i-2]-'0')*10+(s[i-1]-'0') <= 26) { c += a } a, b = b, c } return c }
The above is the detailed content of Go Java algorithm decoding method example code analysis. For more information, please follow other related articles on the PHP Chinese website!