共计 5944 个字符，预计需要花费 15 分钟才能阅读完成。
本文记述笔者的算法学习心得，因为笔者不相熟算法，如有谬误请不吝指正。
九宫格键盘问题
给定一个从数字到字母的映射表：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 window
private 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;
}
}