在一组字符串中查找最长的公共起始子字符串

Question

对于一个相对微不足道的问题,提出最优雅的JavaScript,Ruby或其他解决方案是一项挑战.

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

例如,最长的子串[interspecies, interstelar, interstate]是"inters".但是,我不需要找到"ific" [specifics, terrific].

我已经通过快速编写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 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中的解决方案是首选,但只要您解释正在发生的事情,您就可以在其他语言中展示出聪明的解决方案.请只提供标准库中的代码.

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

我选择了JavaScript的分拣解决方案通过肯纳贝克为"答案",因为它让我觉得既意外和天才.如果我们忽略实际排序的复杂性(让我们想象它是由语言实现无限优化的),解决方案的复杂性只是比较两个字符串.

其他好方案:

• FM的"正则表达式贪婪"需要一两分钟来掌握,但随后它的优雅就会击中你.Yehuda Katz也提出了一个正则表达式解决方案,但它更复杂
• commonprefix在Python中 --Roberto Bonvallet使用了一个用于处理文件系统路径的功能来解决这个问题
• Haskell单线很短,好像它被压缩,很漂亮
• 简单的Ruby单线程

感谢您的参与!从评论中可以看出,我学到了很多东西(甚至是Ruby).

Answer 1

这是一个品味问题,但这是一个简单的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);
}

DEMOS

sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''

Answer 2

在Python中:

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
'inters'

Answer 3

Ruby单行:

l=strings.inject{|l,s| l=l.chop while l!=s[0...l.length];l}

Answer 4

您只需要遍历所有字符串直到它们不同,然后将子字符串提升到这一点.

伪代码:

loop for i upfrom 0
     while all strings[i] are equal
     finally return substring[0..i]

Common Lisp:

(defun longest-common-starting-substring (&rest strings)
  (loop for i from 0 below (apply #'min (mapcar #'length strings))
     while (apply #'char=
                  (mapcar (lambda (string) (aref string i))
                          strings))
     finally (return (subseq (first strings) 0 i))))

Answer 5

我的Haskell单行:

import Data.List

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

编辑:barkmadley对下面的代码做了很好的解释.我还补充一点,haskell使用懒惰评估,所以我们可以懒得使用transpose; 它只会在必要时转置我们的列表以找到公共前缀的结尾.

Answer 6

还有另一种方法:使用正则表达式贪婪.

words = %w(interspecies interstelar interstate)
j = '='
str = ['', *words].join(j)
re = "[^#{j}]*"

str =~ /\A
    (?: #{j} ( #{re} ) #{re} )
    (?: #{j}    \1     #{re} )*
\z/x

p $1

单行,礼貌的mislav(50个字符):

p ARGV.join(' ').match(/^(\w*)\w*(?: \1\w*)*$/)[1]