回答答案 – 解码方式
我试图解决一个问题，我的问题是为什么我的解决方案不起作用？ 。 这是问题，下面是答案。
来自leetcode的问题： http ：//oj.leetcode.com/problems/decode-ways/
使用以下映射将包含来自AZ的字母的消息编码为数字：
'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定包含数字的编码消息，确定解码它的总方式。
例如，给定编码消息“12”，它可以被解码为“AB”（1 2）或“L”（12）。 解码“12”的方式的数量是2。
我的解决方案
我的解决方案的要点是倒退，如果找到分割，则乘以选项的数量。 通过拆分我的意思是数字可以用两种方式解释。 例如：11可以用’aa’或’k’两种方式解释。
public class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') return 0; int decodings = 1; boolean used = false; // Signifies that the prev was already use as a decimal for (int index = s.length()-1 ; index > 0 ; index--) { char curr = s.charAt(index); char prev = s.charAt(index-1); if (curr == '0') { if (prev != '1' && prev != '2') { return 0; } index--; // Skip prev because it is part of curr used = false; } else { if (prev == '1' || (prev == '2' && curr <= '6')) { decodings = decodings * 2; if (used) { decodings = decodings - 1; } used = true; } else { used = false; } } } return decodings; } }
失败的原因如下：
Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948" Output: 3274568 Expected: 589824
这是一个非常有趣的问题。 首先，我将展示如何解决这个问题。 我们将看到使用递归时并不复杂，并且可以使用动态编程解决问题。 我们将生成一个通用解决方案，不会为每个代码点硬编码上限26 。
关于术语的注释：我将使用术语代码点 （CP），而不是Unicode意义上的，但是要引用代码编号1到26 。 每个代码点表示为可变数量的字符。 我还将使用术语编码文本 （ET）和明文 （CT）的明显含义。 在谈论序列或数组时，第一个元素称为头部 。 剩下的元素是尾巴 。
理论前奏
- EC
""有一个解码：CT""。 - EC
"3"可以被解构为'3' + ""，并且具有一个解码。 - EC
"23"可以被解构为'2' + "3"或'23' + ""。 每个尾部都有一个解码，因此整个EC有两个解码。 - EC
"123"可以被解构为'1' + "23"或'12' + "3"。 尾巴分别有两个和一个解码。 整个EC有三个解码。 解构'123' + ""无效 ，因为123 > 26，我们的上限。 - …等等任何长度的EC。
所以给定一个像"123"这样的字符串，我们可以通过在开头找到所有有效的CP，并总结每个尾部的解码数来获得解码的数量。
最困难的部分是寻找有效的头脑。 我们可以通过查看上限的字符串表示来获得头部的最大长度。 在我们的例子中，头部最长可达两个字符。 但并非所有适当长度的头都有效，因为它们也必须≤ 26 。
朴素的递归实现
现在我们已经完成了一个简单（但工作）递归实现的所有必要工作：
static final int upperLimit = 26; static final int maxHeadSize = ("" + upperLimit).length(); static int numDecodings(String encodedText) { // check base case for the recursion if (encodedText.length() == 0) { return 1; } // sum all tails int sum = 0; for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) { String head = encodedText.substring(0, headSize); String tail = encodedText.substring(headSize); if (Integer.parseInt(head) > upperLimit) { break; } sum += numDecodings(tail); } return sum; }
缓存递归实现
显然这不是很有效，因为（对于更长的ET），将对多个相同的尾部进行分析。 此外，我们创建了许多临时字符串，但我们现在就让它成为现实。 我们可以轻松做的一件事就是记住特定尾部的解码次数。 为此，我们使用与输入字符串长度相同的数组：
static final int upperLimit = 26; static final int maxHeadSize = ("" + upperLimit).length(); static int numDecodings(String encodedText) { return numDecodings(encodedText, new Integer[1 + encodedText.length()]); } static int numDecodings(String encodedText, Integer[] cache) { // check base case for the recursion if (encodedText.length() == 0) { return 1; } // check if this tail is already known in the cache if (cache[encodedText.length()] != null) { return cache[encodedText.length()]; } // cache miss -- sum all tails int sum = 0; for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) { String head = encodedText.substring(0, headSize); String tail = encodedText.substring(headSize); if (Integer.parseInt(head) > upperLimit) { break; } sum += numDecodings(tail, cache); // pass the cache through } // update the cache cache[encodedText.length()] = sum; return sum; }
请注意，我们使用Integer[] ，而不是int[] 。 这样，我们可以使用null测试来检查不存在的条目。 这个解决方案不仅正确，而且速度也非常快 – 天真递归在O（解码次数）时间内运行，而memoized版本在O（字符串长度）时间内运行。
迈向DP解决方案
当你在头脑中运行上面的代码时，你会注意到第一次调用整个字符串会有一个缓存未命中，然后计算第一个尾部的解码次数，每次都会错过缓存。 我们可以通过首先从输入结束开始评估尾部来避免这种情况。 因为在整个字符串之前已经评估了所有尾部，所以我们可以删除对缓存未命中的检查。 现在我们也没有任何递归的理由，因为之前的所有结果都已经在缓存中。
static final int upperLimit = 26; static final int maxHeadSize = ("" + upperLimit).length(); static int numDecodings(String encodedText) { int[] cache = new int[encodedText.length() + 1]; // base case: the empty string at encodedText.length() is 1: cache[encodedText.length()] = 1; for (int position = encodedText.length() - 1; position >= 0; position--) { // sum directly into the cache for (int headSize = 1; headSize <= maxHeadSize && headSize + position <= encodedText.length(); headSize++) { String head = encodedText.substring(position, position + headSize); if (Integer.parseInt(head) > upperLimit) { break; } cache[position] += cache[position + headSize]; } } return cache[0]; }
通过注意我们只查询缓存中的最后一个maxHeadSize元素，可以进一步优化该算法。 因此，我们可以使用固定大小的队列而不是数组。 那时，我们将拥有一个在* O（输入长度）时间和O（maxHeadSize）空间中运行的动态编程解决方案。
upperLimit = 26专业化
上面的算法尽可能保持一般，但我们可以针对特定的upperLimit手动专门化它。 这可能很有用，因为它允许我们进行各种优化。 然而，这引入了“魔术数字”，使代码难以维护。 因此，应该在非关键软件中避免这种手动专业化（并且上述算法已经尽可能快）。
static int numDecodings(String encodedText) { // initialize the cache int[] cache = {1, 0, 0}; for (int position = encodedText.length() - 1; position >= 0; position--) { // rotate the cache cache[2] = cache[1]; cache[1] = cache[0]; cache[0] = 0; // headSize == 1 if (position + 0 < encodedText.length()) { char c = encodedText.charAt(position + 0); // 1 .. 9 if ('1' <= c && c <= '9') { cache[0] += cache[1]; } } // headSize == 2 if (position + 1 < encodedText.length()) { char c1 = encodedText.charAt(position + 0); char c2 = encodedText.charAt(position + 1); // 10 .. 19 if ('1' == c1) { cache[0] += cache[2]; } // 20 .. 26 else if ('2' == c1 && '0' <= c2 && c2 <= '6') { cache[0] += cache[2]; } } } return cache[0]; }
与您的代码比较
代码表面上相似。 但是，您对字符的解析更复杂。 您已经引入了一个已used变量，如果设置该变量，则会减少解码计数，以便考虑双字符CP。 这是错的，但我不确定为什么。 主要的问题是你几乎每一步都要加倍计数。 正如我们所看到的，先前的计数被添加 ，并且可能非常不同。
这表明您在没有适当准备的情况下编写了代码。 你可以编写多种软件而不必过多考虑，但在设计算法时你不能没有仔细分析。 对我来说，在纸上设计算法通常很有帮助，并绘制每个步骤的图表（沿着这个答案的“理论前奏”）。 当您过多地考虑要实现的语言时，这一点尤其有用，而对于可能错误的假设则太少。
我建议您阅读“感应certificate”以了解如何编写正确的递归算法。 一旦有了递归解决方案，就可以随时将其转换为迭代版本。
所以这里有一些更简单的方法来解决你的问题。 这非常接近于计算Fibonacci，不同之处在于每个较小尺寸的子问题都有条件检查。 空间复杂度为O（1），时间为O（n）
代码是用C ++编写的。
int numDecodings(string s) { if( s.length() == 0 ) return 0; int j = 0; int p1 = (s[j] != '0' ? 1 : 0); // one step prev form j=1 int p2 = 1; // two step prev from j=1, empty int p = p1; for( int j = 1; j < s.length(); j++ ) { p = 0; if( s[j] != '0' ) p += p1; if( isValidTwo(s, j-1, j) ) p += p2; if( p==0 ) // no further decoding necessary, break; // as the prefix 0--j is has no possible decoding. p2 = p1; // update prev for next j+1; p1 = p; } return p; } bool isValidTwo(string &s, int i, int j) { int val= 10*(s[i]-'0')+s[j]-'0'; if ( val <= 9 ) return false; if ( val > 26 ) return false; return true; }
这是我解决问题的代码。 我使用DP ，我认为很清楚。
用Java编写
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[0] = 1; dp[1] = s.charAt(0) != '0' ? 1 : 0; for(int i = 2; i <= n; i++){ int first = Integer.valueOf(s.substring(i-1,i)); int second = Integer.valueOf(s.substring(i-2,i)); if(first >= 1 && first <= 9){ dp[i] += dp[i-1]; } if(second >= 10 && second <= 26){ dp[i] += dp[i-2]; } } return dp[n]; }
}
由于我自己在解决这个问题，这是我的解决方案和推理。 可能我会大部分重复amon所写的内容，但也许有人会发现它有用。 它也是c＃而不是java。
假设我们输入“12131”并希望获得所有可能的解码字符串。 直接递归解决方案将从左到右迭代，获得有效的1和2位数头，并递归调用尾部函数。
我们可以使用树来可视化它：
有5个叶子，这是所有可能的解码字符串的数量。 还有3个空叶，因为31号不能解码成字母，所以这些叶子无效。
算法可能如下所示：
public IList Decode(string s) { var result = new List (); if (s.Length <= 2) { if (s.Length == 1) { if (s[0] != '0') result.Add(this.ToASCII(s)); } else if (s.Length == 2) { if (s[0] != '0' && s[1] != '0') result.Add(this.ToASCII(s.Substring(0, 1)) + this.ToASCII(s.Substring(1, 1))); if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26) result.Add(this.ToASCII(s)); } } else { for (int i = 1; i <= 2; ++i) { string head = s.Substring(0, i); if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26) { var tails = this.Decode(s.Substring(i)); foreach (var tail in tails) result.Add(this.ToASCII(head) + tail); } } } return result; } public string ToASCII(string str) { int number = int.Parse(str); int asciiChar = number + 65 - 1; // A in ASCII = 65 return ((char)asciiChar).ToString(); }
我们必须处理从0（“0”，“03”等）开始，大于26的数字。
因为在这个问题中我们只需要计算解码方式，而不是实际的字符串，我们可以简化这段代码：
public int DecodeCount(string s) { int count = 0; if (s.Length <= 2) { if (s.Length == 1) { if (s[0] != '0') count++; } else if (s.Length == 2) { if (s[0] != '0' && s[1] != '0') count++; if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26) count++; } } else { for (int i = 1; i <= 2; ++i) { string head = s.Substring(0, i); if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26) count += this.DecodeCount(s.Substring(i)); } } return count; }
该算法的问题在于我们多次计算相同输入字符串的结果。 例如，有3个以31结尾的节点：ABA31，AU31，LA31。 还有2个节点以131结尾：AB131，L131。 我们知道如果节点以31结尾，它只有一个子节点，因为31只能以一种方式解码到CA. 同样，我们知道如果字符串以131结尾，则它有2个子节点，因为131可以解码为ACA或LA。 因此，我们可以将其缓存在map中，而不是重新计算它，其中key是string（例如：“131”），value是解码方式的数量：
public int DecodeCountCached(string s, Dictionary cache) { if (cache.ContainsKey(s)) return cache[s]; int count = 0; if (s.Length <= 2) { if (s.Length == 1) { if (s[0] != '0') count++; } else if (s.Length == 2) { if (s[0] != '0' && s[1] != '0') count++; if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26) count++; } } else { for (int i = 1; i <= 2; ++i) { string head = s.Substring(0, i); if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26) count += this.DecodeCountCached(s.Substring(i), cache); } } cache[s] = count; return count; }
我们可以进一步完善这一点。 我们可以使用length来代替使用字符串作为键，因为缓存的内容始终是输入字符串的尾部。 所以不是缓存字符串：“1”，“31”，“131”，“2131”，“12131”我们可以缓存尾部长度：1,2,3,4,5：
public int DecodeCountDPTopDown(string s, Dictionary cache) { if (cache.ContainsKey(s.Length)) return cache[s.Length]; int count = 0; if (s.Length <= 2) { if (s.Length == 1) { if (s[0] != '0') count++; } else if (s.Length == 2) { if (s[0] != '0' && s[1] != '0') count++; if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26) count++; } } else { for (int i = 1; i <= 2; ++i) { string head = s.Substring(0, i); if (s[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26) count += this.DecodeCountDPTopDown(s.Substring(i), cache); } } cache[s.Length] = count; return count; }
这是递归的自上而下的动态编程方法。 我们从开始开始，然后递归计算尾部的解决方案，并记住这些结果以供进一步使用。
我们可以将其转换为自下而上的迭代DP解决方案。 我们从最后开始，并像以前的解决方案一样缓存切片的结果。 我们可以使用数组而不是map，因为键是整数：
public int DecodeCountBottomUp(string s) { int[] chache = new int[s.Length + 1]; chache[0] = 0; // for empty string; for (int i = 1; i <= s.Length; ++i) { string tail = s.Substring(s.Length - i, i); if (tail.Length == 1) { if (tail[0] != '0') chache[i]++; } else if (tail.Length == 2) { if (tail[0] != '0' && tail[1] != '0') chache[i]++; if (tail[0] != '0' && int.Parse(tail) > 0 && int.Parse(tail) <= 26) chache[i]++; } else { if (tail[0] != '0') chache[i] += chache[i - 1]; if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26) chache[i] += chache[i - 2]; } } return chache.Last(); }
有些人甚至进一步简化它，用值1初始化cache [0]，这样就可以摆脱tail.Length == 1和tail.Length == 2的条件。 对我来说这是不直观的技巧，因为很明显，对于空字符串，有0个解码方式不是1，所以在这种情况下必须添加附加条件来处理空输入：
public int DecodeCountBottomUp2(string s) { if (s.Length == 0) return 0; int[] chache = new int[s.Length + 1]; chache[0] = 1; chache[1] = s.Last() != '0' ? 1 : 0; for (int i = 2; i <= s.Length; ++i) { string tail = s.Substring(s.Length - i, i); if (tail[0] != '0') chache[i] += chache[i - 1]; if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26) chache[i] += chache[i - 2]; } return chache.Last(); }
我的解决方案基于这样的想法：特定子字符串中的项（char / digit）的排列在不同的子字符串中完全独立于相同的子字符串。 因此，我们需要将每种独立方式相乘以获得总路数。
// nc is the number of consecutive 1's or 2's in a substring. // Returns the number of ways these can be arranged within // themselves to a valid expr. int ways(int nc){ int n = pow(2, (nc/2)); //this part can be memorized using map for optimization int m = n; if (nc%2) { m *= 2; } return n + m - 1; } bool validTens(string A, int i){ return (A[i] == '1' || (A[i] == '2' && A[i+1] <= '6')); } int numDecodings(string A) { int ans = 1; int nc; if ((A.length() == 0)||(A[0] == '0')) return 0; for(int i = 1; i < A.length();i++){ if(A[i] == '0' && validTens(A, i-1) == false) return 0; //invalid string while(i < A.length() && validTens(A, i-1)) { if(A[i] == '0'){ //think of '110' or '1210', the last two digits must be together if(nc > 0) nc--; } else nc++; i++; } ans *= ways(nc); nc = 0; } return ans; }