javascript - 在一组字符串中找到最长的公共(public)起始子字符串

Question

关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。












这个问题似乎与 help center 中定义的范围内的编程无关。 .


6年前关闭。















锁定。这个问题及其答案是locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或交互。








这是为一个相对琐碎的问题想出最优雅的 JavaScript、Ruby 或其他解决方案的挑战。

这个问题是 Longest common substring problem 的一个更具体的情况。 .我只需要找到最长的公共(public)开始 数组中的子字符串。这大大简化了问题。

例如，[interspecies, interstelar, interstate] 中最长的子串是“中间人”。但是，我不需要在 [specifics, terrific] 中找到“ific”。 .

作为我的 answer about shell-like tab-completion 的一部分，我通过快速编写 JavaScript 解决方案解决了这个问题。 (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)
}

这个 code is available in this Gist以及 Ruby 中的类似解决方案。您可以将要点克隆为 git repo 以进行尝试:

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

我对这些解决方案不太满意。我有一种感觉，它们可能会以更优雅的方式和更少的执行复杂性来解决——这就是我发布这个挑战的原因。

我将接受我认为最优雅或最简洁的解决方案作为答案。例如，这是我想出的一个疯狂的 Ruby hack——定义 &字符串上的运算符:

# 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 的解决方案是首选，但你可以用其他语言展示聪明的解决方案，只要你解释发生了什么。请仅使用标准库中的代码。

更新:我最喜欢的解决方案

我选择了 JavaScript sorting solution由 kennebec作为“答案”，因为它让我觉得既出乎意料又是天才。如果我们忽略实际排序的复杂性(假设它被语言实现无限优化)，解决方案的复杂性只是比较两个字符串。

其他很棒的解决方案:

"regex greed" by FM 需要一两分钟才能掌握，但随后它的优雅就让你眼前一亮。 Yehuda Katz 还制作了 a regex solution , 但它更复杂

commonprefix in Python — Roberto Bonvallet 使用了一个用于处理文件系统路径的特性来解决这个问题

Haskell one-liner很短，好像被压缩了一样，很漂亮

the straightforward Ruby one-liner

感谢参与!正如您从评论中看到的，我学到了很多东西(甚至是关于 Ruby)。

Answer 1

这是一个口味问题，但这是一个简单的 javascript 版本:
它对数组进行排序，然后只查看第一项和最后一项。

//数组中最长的公共(public)起始子串

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'])                           //=> ''