关于算法:递归迭代和动态规划以九宫格键盘为例

本文记述笔者的算法学习心得，因为笔者不相熟算法，如有谬误请不吝指正。

给定一个从数字到字母的映射表：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;
  }
}

关于算法:递归迭代和动态规划以九宫格键盘为例

九宫格键盘问题

根底版的解法

递归法

迭代法

难度加强版的解法

递归法

递归法的性能优化

动静规划法

附录