这是为一个相对琐碎的问题想出最优雅的 JavaScript、Ruby 或其他解决方案的挑战。
这个问题是最长公共子串问题的一个更具体的例子。我只需要在数组中找到最长的公共起始子字符串。这大大简化了问题。
例如，最长的子串[interspecies, interstelar, interstate]是“inters”。但是，我不需要在[specifics, terrific].
我已经通过在 JavaScript 中快速编写一个解决方案来解决这个问题，作为我关于 shell-like tab-completion ( test page here )的答案的一部分。这是该解决方案，稍作调整：
function common_substring(data) {
var i, ch, memo, idx = 0
do {
memo = null
for (i=0; i < data.length; i++) {
ch = data[i].charAt(idx)
if (!ch) break
if (!memo) memo = ch
else if (ch != memo) break
}
} while (i == data.length && idx < data.length && ++idx)
return (data[0] || '').slice(0, idx)
}
此Gist 中提供了此代码以及Ruby 中的类似解决方案。您可以将要点克隆为 git repo 以进行尝试：
$ git clone git://gist.github.com/257891.git substring-challenge
我对这些解决方案不太满意。我有一种感觉，它们可能会以更优雅的方式和更少的执行复杂性来解决——这就是我发布这个挑战的原因。
我将接受我认为最优雅或最简洁的解决方案作为答案。例如，这是我想出的一个疯狂的 Ruby hack——&在 String 上定义运算符：
# works with Ruby 1.8.7 and above
class String
def &(other)
difference = other.to_str.each_char.with_index.find { |ch, idx|
self[idx].nil? or ch != self[idx].chr
}
difference ? self[0, difference.last] : self
end
end
class Array
def common_substring
self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
end
end
JavaScript 或 Ruby 的解决方案是首选，但你可以用其他语言展示聪明的解决方案，只要你解释发生了什么。请仅使用标准库中的代码。
更新：我最喜欢的解决方案
我选择了kennebec的JavaScript 排序解决方案作为“答案”，因为它让我觉得既意外又天才。如果我们忽略实际排序的复杂性（让我们想象它被语言实现无限优化），解决方案的复杂性只是比较两个字符串。
其他很棒的解决方案：
- FM 的“regex greed”需要一两分钟才能掌握，但随后它的优雅就让你眼前一亮。Yehuda Katz 也做了一个正则表达式解决方案，但它更复杂
commonprefix在 Python 中——Roberto Bonvallet 使用了一个用于处理文件系统路径的特性来解决这个问题- Haskell one-liner很短，好像被压缩了一样，很漂亮
- 简单的 Ruby 单线
感谢参与！正如您从评论中看到的，我学到了很多东西（甚至是关于 Ruby）。