首页 / 问题 / 正文

找到一组字符串中最长的公共前缀字符串

39 投票
31 回答
48375 浏览
提问于 2025-04-15 17:06

这是一个挑战，目的是找出最优雅的 JavaScript、Ruby 或其他语言的解决方案，来解决一个相对简单的问题。

这个问题是 最长公共子串问题 的一个更具体的情况。我只需要在一个数组中找到最长的公共起始子串。这大大简化了问题。

举个例子，在 [interspecies, interstelar, interstate] 中，最长的起始子串是 "inters"。不过，我不需要在 [specifics, terrific] 中找到 "ific"。

我通过快速编写 JavaScript 代码解决了这个问题，作为我关于 类似于 shell 的标签补全 的回答的一部分（这里是测试页面）。以下是我稍微调整过的解决方案：

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 解决方案。你可以把这个 gist 克隆为 git 仓库来试试：

$ git clone git://gist.github.com/257891.git substring-challenge

我对这些解决方案并不是很满意。我觉得可以用更优雅、更简单的方法来解决这问题——这就是我发起这个挑战的原因。

我会选择我认为最优雅或简洁的解决方案作为答案。比如，这里有一个我想到的疯狂 Ruby 黑科技——在字符串上定义 & 操作符：

# 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 排序解决方案 作为“答案”，因为它让我觉得既意外又聪明。如果我们忽略实际排序的复杂性（假设语言实现已经优化到极致），那么这个解决方案的复杂性仅仅是比较两个字符串。

其他很棒的解决方案：

感谢大家的参与！从评论中可以看出，我学到了很多东西（甚至关于 Ruby 的知识）。

正则表达式 代码优化 编程语言 数据结构 字符串处理 自动补全 最长公共前缀 算法挑战

31 个回答

9

这是我写的Haskell一行代码：

import Data.List

commonPre :: [String] -> String
commonPre = map head . takeWhile (\(x:xs)-> all (==x) xs) . transpose

补充说明：barkmadley对下面的代码做了很好的解释。我还想补充一点，Haskell使用的是惰性求值，所以我们在使用transpose的时候可以不那么着急；它只会在需要的时候才去转置我们的列表，直到找到公共前缀的结尾。

回答于 2025-04-15 由 Python大师
分享 举报
38

在Python中：

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
'inters'
回答于 2025-04-15 由 Python大师
分享 举报
55

这完全是个人喜好，不过这是一个简单的JavaScript版本：

它会对数组进行排序，然后只关注第一个和最后一个元素。

//在数组中查找最长的公共起始子串

function sharedStart(array){
    var A= array.concat().sort(), 
    a1= A[0], a2= A[A.length-1], L= a1.length, i= 0;
    while(i<L && a1.charAt(i)=== a2.charAt(i)) i++;
    return a1.substring(0, i);
}

示例

sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''
回答于 2025-04-15 由 Python大师
分享 举报

撰写回答