本文记述笔者的算法学习心得，因为笔者不相熟算法，如有谬误请不吝指正。
九宫格键盘问题
给定一个从数字到字母的映射表：1 => [a, b, c], 2 => [d, e, f], 3=> [g, h, i], ......，实现一个函数List<String> calculate(String input)，若用户输出任意的数字串，要根据映射表转换每一个数字，返回所有可能的转换后果。例如，若输出“12”会失去ad, ae, af, bd, be, bf, cd, ce, cf这9个后果；若输出“123”会失去27个后果。
以上是此题的根底版，还有一个难度加强版：映射表的键还能够是数字组合，如12 => [x], 23 => [y]。若输出“12”会有10个后果，还会有x这1个后果（总共10个后果）；若输出“123”，岂但有之前的27个后果，还会有xg, xh, xi, ay, by, cy这6个后果（总共33个后果）。
根底版的解法
能够用递归法也能够用迭代法，两种办法是等价的。以下是算法思维和实现代码。
递归法
递归法的思维是继续把问题降解为子问题，直到子问题足够小。例如，calculate("123")等价于calculate("1") * calculate("23")，而calculate("23")等价于calculate("2") * calculate("3")。这里引入了一种非凡的汇合乘法，能把如[a, b, c]和[d, e, f]这样的两个汇合相乘失去9个后果（即输出“12”对应的后果），这种乘法能够用一个函数来实现。如此就清晰地表述了递归法的算法框架。
实现代码为
static List<String> calculate(String input) { if (input.isEmpty()) { return Collections.emptyList(); } String key = String.valueOf(input.charAt(0)); List<String> values = mappings.get(key); String substring = input.substring(1); if (substring.isEmpty()) { return values; } else { return product(values, calculate(substring)); }}// 乘法static List<String> product(List<String> lefts, List<String> rights) { List<String> results = new ArrayList<>(); for (String left : lefts) { for (String right : rights) { results.add(left + right); } } return results;}迭代法
迭代法的思维是顺次解决输出的每一位，用已得后果集示意以后状态，记住和更新以后状态。例如，calculate(“123”)的处理过程是，第一步解决”1”，失去初始状态[a, b, c]，第二步解决”2”，让以后状态[a, b, c]乘以“2”对应的[d, e, f]，失去新状态[ad, ae, af, bd, be, bf, cd, ce, cf]，第三步解决”3”，让以后状态乘以”3”对应的[g, h, i]，失去新状态，此时输出值已全副解决实现。
实现代码为
static List<String> calculate(String input) { List<String> results = Collections.emptyList(); for (int i = 0; i < input.length(); i++) { String key = String.valueOf(input.charAt(i)); List<String> values = mappings.get(key); if (results.isEmpty()) { results = values; } else { results = product(results, values); } } return results;}static List<String> product(List<String> lefts, List<String> rights) { List<String> results = new ArrayList<>(); for (String left : lefts) { for (String right : rights) { results.add(left + right); } } return results;}难度加强版的解法
根底版间接把每1位数字作为key，用mappings.get(key)获取映射值。而难度加强版面对不等长的key，须要换一个形式，遍历mappings中的每一个key，判断以后输出是否以这个key结尾，若是，就采纳这个key的映射值，同时从以后输出去掉这个key，而后持续解决残余输出。
根底版的递归法略加修改就能失去难度加强版的解法。迭代法不能批改失去新解法，因为每一步可能产生多个步长不同的分支，这些分支所需解决的残余输出是不同的，不能枯燥迭代，用算法实践来说，因为这里的递归法不是尾递归，因而没有等价的迭代法版本。能够用栈或队列将递归计算转换为连续（continuation）来实现迭代计算，其实相当于模仿了递归，这个留给读者自行实现。
其实迭代法能够更高效地实现，然而要应用动静规划法。
递归法
实现代码为
static List<String> calculate(String input) { if (input.isEmpty()) { return Collections.emptyList(); } List<String> results = new ArrayList<>(); for (String key : mappings.keySet()) { if (input.startsWith(key)) { List<String> values = mappings.get(key); if (values == null) { throw new IllegalArgumentException("Unrecognized input"); } String substring = input.substring(key.length()); if (substring.isEmpty()) { results.addAll(values); } else { results.addAll(product(values, calculate(substring))); } } } return results;}// 乘法static List<String> product(List<String> lefts, List<String> rights) { List<String> results = new ArrayList<>(); for (String left : lefts) { for (String right : rights) { results.add(left + right); } } return results;}递归法的性能优化
来找找优化点。递归过程有很多反复的计算，能够用memoization技术搞一个缓存来提速，据测试能提速一倍，缓存的数据结构能够用哈希表或数组来实现。哈希表以calculate()的input参数作为键，以calculate()的后果作为值；数组以input.length()作为索引值，以calculate()的后果作为元素值。若输出规模为n，缓存的空间复杂度为O(n)。这个就交给读者自行实现吧。
results.addAll(product(values, calculate(substring)));这行是能够优化的，product()返回一个新建的list，这个list又被复制到results里，存在一些内存调配和复制的开销。如果product()能间接输入到results而不是返回一个list，就不必新建和复制一个list。据测试能提速10%左右。
代码批改为
// 调用处这么改product(values, calculate(substring), results);// 定义处这么改static List<String> product(List<String> lefts, List<String> rights, List<String> results) { for (String left : lefts) { for (String right : rights) { results.add(left + right); } }}String substring = input.substring(key.length());这行如同也能够优化，substring()返回一个新建的子字符串，存在一些内存调配和复制的开销。其实，在旧版JVM上有一个优化，substring()是像subList()一样的视图对象，间接援用原始字符串而不是创立正本，但新版JVM为了避免内存透露而勾销了这一优化（大型原始字符串已不再应用，但仍被子字符串援用而无奈开释空间）。咱们能够手动实现一个StringView类来做同样的优化，但substring()的调用次数不多，因而对理论性能没有什么晋升。这个技术还是比拟有意思的，StringView的实现在文尾的附录提供。
动静规划法
动静规划法能达到和memoization差不多甚至更快的速度，因为它也防止了反复的计算，而且空间复杂度只有O(1)。
《算法概论》和《算法设计》这两本算法教材都讲到，动静布局不可能用递归来实现。动静布局的思维是从初始状态登程，一步步产生新状态，每一个新状态是从之前的一个或多个状态失去的，实现起来像一个状态机，因而不可能用递归来表白。对于这道题，能够继续扫描输出串，每一步向前扫一位，用以后已扫过的字符序列来示意以后状态，若以后状态以某个key结尾，则把此key的映射值乘到它所对应的“上一步”的后果集上，把新的后果集保留到缓存。这个“上一步”是哪一步呢？不是简略地回退一位，而是把方才扫到的key从以后状态去掉，就能回退到上一步的状态（相当于回退了key.length位），因为每一步都把后果集保留到缓存了，因而只有查问缓存就能失去上一步的后果集。缓存以回退位数为键，因为回退位数最多也不可能超过最长的key的length，因而缓存是一个大小不超过这个数的滑动窗口，新的值进来就把最旧的值挤掉，只需常数级空间。
实现代码为
static List<String> calculate(String input) { String state = ""; List<String> results = new ArrayList<>(); Cache cache = new Cache(); for (int i = 0; i < input.length(); i++) { state += input.charAt(i); List<String> newResults = new ArrayList<>(); for (String key : mappings.keySet()) { if (state.endsWith(key)) { List<String> prevResult = cache.get(key.length()); List<String> values = mappings.get(key); if (prevResult == null) { newResults.addAll(values); } else { newResults.addAll(product(prevResult, values)); } } } results = newResults; cache.put(results); } return results;}static List<String> product(List<String> lefts, List<String> rights) { List<String> results = new ArrayList<>(); for (String left : lefts) { for (String right : rights) { results.add(left + right); } } return results;}// Sliding windowprivate static class Cache { private int maxLength = mappings.keySet().stream().map(String::length).max(Integer::compareTo).get(); private LinkedList<List<String>> queue = new LinkedList<>(); List<String> get(int lookBackLength) { if (queue.size() < lookBackLength) { return null; } return queue.get(lookBackLength - 1); } void put(List<String> solutions) { if (queue.size() == maxLength) { queue.removeLast(); } queue.offerFirst(solutions); }}附录
StringView的实现代码
class StringView { private final String string; private final int offset; StringView(String string, int offset) { if (offset > string.length()) { throw new IllegalArgumentException("offset should be within string length"); } this.string = string; this.offset = offset; } StringView subview(int additionalOffset) { return new StringView(string, offset + additionalOffset); } boolean isEmpty() { return offset == string.length(); } boolean startsWith(String key) { int keyLength = key.length(); if (string.length() < offset + keyLength) { return false; } for (int i = 0; i < keyLength; i++) { if (key.charAt(i) != string.charAt(i + offset)) { return false; } } return true; }}