查找一组string中最长的共同起始子string

这是一个挑战，拿出最优雅的JavaScript，ruby或其他解决scheme，以相对微不足道的问题。

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

例如， [interspecies, interstelar, interstate]最长的子串是“inters”。 但是，我不需要在[specifics, terrific]find“定义”。

我已经解决了这个问题，通过在JavaScript中快速编写一个解决scheme，作为我关于shell-like tab-completion （ testing页面 ）的答案的一部分。 这个解决scheme略有调整：

 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中使用类似的解决scheme。 你可以把gist作为一个git repo来试用一下：

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

我对这些解决scheme并不满意。 我有一种感觉，他们可以用更多的优雅和更less的执行复杂性来解决 – 这就是为什么我要发布这个挑战。

我将接受作为答案我find最优雅或简洁的解决scheme。 这里是一个疯狂的ruby黑客我想出来 – 在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的解决scheme是首选，但只要您解释发生了什么，您可以在其他语言中展示聪明的解决scheme。 请只从标准库的代码。

更新：我最喜欢的解决scheme

我select了肯尼贝克的JavaScriptsorting解决scheme作为“答案”，因为它让我感到意外和天才。 如果我们忽视实际sorting的复杂性（让我们假设它是由语言实现无限优化），解决scheme的复杂性只是比较两个string。

其他很棒的解决

• FM的“正则expression式贪婪”需要一两分钟的时间才能掌握，但是它的高雅却击中了你。 耶胡达卡茨也提出了一个正则expression式的解决scheme ，但它更复杂
• Python中的commonprefix – Roberto Bonvallet使用了一个用于处理文件系统path的function来解决这个问题
• Haskell单行程很短，好像被压缩了一样，很漂亮
• 直接的ruby单线

感谢参与！ 从评论中可以看出，我学到了很多（甚至是Ruby）。

Answer 1

这是一个味道的问题，但这是一个简单的JavaScript版本：它对数组进行sorting，然后只看第一个和最后一个项目。

//数组中最长的公共起始子string

 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

我的Haskell单行：

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

编辑：barkmadley给了下面的代码一个很好的解释。 我还要补充一点，haskell使用懒惰评估，所以我们可以懒惰我们使用transpose ; 它只会转换我们的名单，以便find共同前缀的结尾。

Answer 5

你只需要遍历所有的string，直到它们不同，然后把子string加到这个点上。

伪代码：

 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 6

还有另一种方法：使用正则expression式贪婪。

 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] 

Answer 7

在Python中，我不会使用任何东西，除了我在另一个答案中显示的现有的commonprefix函数，但我不禁要重新发明轮子:P 。 这是我基于迭代器的方法：

 >>> a = 'interspecies interstelar interstate'.split() >>> >>> from itertools import takewhile, chain, izip as zip, imap as map >>> ''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a))))) 'inters' 

编辑：这是如何工作的解释。

zip生成一个元素的元素：

 In [6]: list(zip(*a)) # here I use list() to expand the iterator Out[6]: [('i', 'i', 'i'), ('n', 'n', 'n'), ('t', 't', 't'), ('e', 'e', 'e'), ('r', 'r', 'r'), ('s', 's', 's'), ('p', 't', 't'), ('e', 'e', 'a'), ('c', 'l', 't'), ('i', 'a', 'e')] 

通过映射对这些项目的set ，我得到一系列独特的字母：

 In [7]: list(map(set, _)) # _ means the result of the last statement above Out[7]: [set(['i']), set(['n']), set(['t']), set(['e']), set(['r']), set(['s']), set(['p', 't']), set(['a', 'e']), set(['c', 'l', 't']), set(['a', 'e', 'i'])] 

takewhile(predicate, items)成分，而谓词为真; 在这个特定的情况下，当set s有一个元素，即所有的单词在那个位置上都有相同的字母：

 In [8]: list(takewhile(lambda s: len(s) == 1, _)) Out[8]: [set(['i']), set(['n']), set(['t']), set(['e']), set(['r']), set(['s'])] 

在这一点上，我们有一套可迭代的集合，每个集合都包含我们要查找的前缀的一个字母。 为了构造string，我们将它们链接成一个单一的迭代器，从中我们得到字母join到最终的string中。

使用迭代器的神奇之处在于，所有项目都是按需生成的，因此，当停止询问项目时，压缩将停止在那一点，并且不会执行不必​​要的工作。 在我的一行中的每个函数调用都有一个隐含for和隐含的break 。

Answer 8

这可能不是最简洁的解决scheme（取决于如果你已经有一个库），但一个优雅的方法是使用一个trie。 我使用尝试在我的Scheme解释器中实现选项卡完成：

http://github.com/jcoglan/heist/blob/master/lib/trie.rb

例如：

 tree = Trie.new %w[interspecies interstelar interstate].each { |s| tree[s] = true } tree.longest_prefix('') #=> "inters" 

我也使用它们来匹配Bayeux协议的通配符和通配符。 看到这些：

http://github.com/jcoglan/faye/blob/master/client/channel.js

http://github.com/jcoglan/faye/blob/master/lib/faye/channel.rb

Answer 9

只是为了它的乐趣，这是用（SWI-）PROLOG写的一个版本：

 common_pre([[C|Cs]|Ss], [C|Res]) :- maplist(head_tail(C), [[C|Cs]|Ss], RemSs), !, common_pre(RemSs, Res). common_pre(_, []). head_tail(H, [H|T], T). 

运行：

 ?- S=["interspecies", "interstelar", "interstate"], common_pre(S, CP), string_to_list(CPString, CP). 

得到：

 CP = [105, 110, 116, 101, 114, 115], CPString = "inters". 

说明：

（SWI-）PROLOG将string视为字符代码（数字）的列表。 所有谓词common_pre/2都是recursion地进行模式匹配，从所有列表（所有string[[C|Cs]|Ss] [C|Cs] ）列表中的第一个列表（string[C|Cs] ）的开头select第一个代码（ C ） 如果它对所有列表（string）的所有（剩余）头部是通用的，则将匹配的代码C附加到结果，否则结束。

干净，简单，高效… 🙂

Answer 10

基于@ Svantealgorithm的 JavaScript版本：

 function commonSubstring(words){ var iChar, iWord, refWord = words[0], lRefWord = refWord.length, lWords = words.length; for (iChar = 0; iChar < lRefWord; iChar += 1) { for (iWord = 1; iWord < lWords; iWord += 1) { if (refWord[iChar] !== words[iWord][iChar]) { return refWord.substring(0, iChar); } } } return refWord; } 

Answer 11

结合kennebec ， Florian F和jberryman的答案可以得出以下Haskell单行：

 commonPrefix l = map fst . takeWhile (uncurry (==)) $ zip (minimum l) (maximum l) 

使用Control.Arrow可以得到一个无点的表单：

 commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum) 

Answer 12

 Python 2.6 (r26:66714, Oct 4 2008, 02:48:43) >>> a = ['interspecies', 'interstelar', 'interstate'] >>> print a[0][:max( [i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1] ) + 1] inters 

• i for i in range(min(map(len, a))) ，最大查找次数不能大于最短string的长度; 在这个例子中，这将评估为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• len(set(map(lambda e: e[i], a))) ，1）为列表中的每个string创build一个第i-th字符的数组; 2）制定一个计划; 3）确定集合的大小

• [i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1] ，那么只包含字符的大小，的集合是1（该位置的所有字符都是相同的）。 在这里它将评估为[0, 1, 2, 3, 4, 5]

• 最后取max ，加一个，得到子串…

注意：以上不适用于a = ['intersyate', 'intersxate', 'interstate', 'intersrate'] ，但是这将会：

  >>> index = len( filter(lambda l: l[0] == l[1], [ x for x in enumerate( [i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1] )])) >>> a[0][:index] inters 

Answer 13

如果你不是太在意最终的performance，看起来并不复杂：

 def common_substring(data) data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] } end 

注入的有用特征之一是能够与arrays的第一个元素进行预先结合。 这避免了零备注检查。

 puts common_substring(%w[ interspecies interstelar interstate ]).inspect # => "inters" puts common_substring(%w[ feet feel feeble ]).inspect # => "fee" puts common_substring(%w[ fine firkin fail ]).inspect # => "f" puts common_substring(%w[ alpha bravo charlie ]).inspect # => "" puts common_substring(%w[ fork ]).inspect # => "fork" puts common_substring(%w[ fork forks ]).inspect # => "fork" 

更新：如果高尔夫是这里的比赛，那么67个字符：

 def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end 

Answer 14

这个和Roberto Bonvallet的解决scheme非常相似，除了ruby。

 chars = %w[interspecies interstelar interstate].map {|w| w.split('') } chars[0].zip(*chars[1..-1]).map { |c| c.uniq }.take_while { |c| c.size == 1 }.join 

第一行用一个字符数组replace每个单词。 接下来，我使用zip创build这个数据结构：

[["i", "i", "i"], ["n", "n", "n"], ["t", "t", "t"], ...

map和uniq减less到[["i"],["n"],["t"], ...

take_while取出字符，直到find大小不是1的字符（表示不是所有的字符都是相同的）。 最后，我把他们一起回来。

Answer 15

被接受的解决scheme被破坏了（例如，它返回a像['a', 'ba']string）。 修复非常简单，你只需要改变3个字符（从indexOf(tem1) == -1到indexOf(tem1) != 0 ），这个函数可以按照预期工作。

不幸的是，当我试图编辑解决错误的答案时，SO告诉我“编辑必须至less有6个字符”。 我可以通过改进命名和可读性来改变那些3个字符，但是感觉有点太多了。

所以，下面是肯尼贝克解决scheme的一个固定和改进的版本（至less从我的angular度来看）：

 function commonPrefix(words) { max_word = words.reduce(function(a, b) { return a > b ? a : b }); prefix = words.reduce(function(a, b) { return a > b ? b : a }); // min word while(max_word.indexOf(prefix) != 0) { prefix = prefix.slice(0, -1); } return prefix; } 

（在jsFiddle上 ）

请注意，它使用reduce方法（JavaScript 1.8）来查找字母数字最大/最小值，而不是对数组进行sorting，然后获取数组的第一个和最后一个元素。

Answer 16

在阅读这些答案的时候，所有的function编程，sorting和正则expression式都是这样的，我只是想：C有点什么问题？ 所以这是一个愚蠢的小程序。

 #include <stdio.h> int main (int argc, char *argv[]) { int i = -1, j, c; if (argc < 2) return 1; while (c = argv[1][++i]) for (j = 2; j < argc; j++) if (argv[j][i] != c) goto out; out: printf("Longest common prefix: %.*s\n", i, argv[1]); } 

编译它，运行你的string列表作为命令行参数，然后upvote我使用goto ！

Answer 17

以下是在Ruby中使用正则expression式的解决scheme：

 def build_regex(string) arr = [] arr << string.dup while string.chop! Regexp.new("^(#{arr.join("|")})") end def substring(first, *strings) strings.inject(first) do |accum, string| build_regex(accum).match(string)[0] end end 

Answer 18

我会做以下几点：

1. 以数组的第一个string作为初始的起始子string 。
2. 取数组的下一个string并比较字符，直到达到其中一个string的末尾或发现不匹配。 如果发现不匹配，则将起始子string缩小到发现不匹配的长度。
3. 重复第2步，直到所有的string都经过testing。

这是一个JavaScript实现：

 var array = ["interspecies", "interstelar", "interstate"], prefix = array[0], len = prefix.length; for (i=1; i<array.length; i++) { for (j=0, len=Math.min(len,array[j].length); j<len; j++) { if (prefix[j] != array[i][j]) { len = j; prefix = prefix.substr(0, len); break; } } } 

Answer 19

而不是sorting，你可以得到最小和最大的string。

对我来说，计算机程序的优雅是速度和简单的平衡。 它不应该做不必要的计算，它应该很简单，使其正确性明显。

我可以把分类解决scheme称为“聪明”，但不是“优雅”。

Answer 20

通常使用成熟的开源库而不是自己动手更优雅。 那么，如果它不完全适合你的需求，你可以扩展它或修改它来改进它，让社区决定是否属于图书馆。

diff-lcs是最不常见的子string的一个很好的ruby。

Answer 21

我在Java中的解决scheme：

 public static String compute(Collection<String> strings) { if(strings.isEmpty()) return ""; Set<Character> v = new HashSet<Character>(); int i = 0; try { while(true) { for(String s : strings) v.add(s.charAt(i)); if(v.size() > 1) break; v.clear(); i++; } } catch(StringIndexOutOfBoundsException ex) {} return strings.iterator().next().substring(0, i); } 

Answer 22

高尔夫JS解决scheme只是为了好玩：

 w=["hello", "hell", "helen"]; c=w.reduce(function(p,c){ for(r="",i=0;p[i]==c[i];r+=p[i],i++){} return r; }); 

Answer 23

这是一个有效的解决scheme在ruby。 我基于高/低猜测游戏的策略的想法，你在迭代中最长的前缀零。

有人纠正我，如果我错了，但我认为复杂性是O（n日志n），其中n是最短的string的长度和string的数量被认为是一个常数。

 def common(strings) lo = 0 hi = strings.map(&:length).min - 1 return '' if hi < lo guess, last_guess = lo, hi while guess != last_guess last_guess = guess guess = lo + ((hi - lo) / 2.0).ceil if strings.map { |s| s[0..guess] }.uniq.length == 1 lo = guess else hi = guess end end strings.map { |s| s[0...guess] }.uniq.length == 1 ? strings.first[0...guess] : '' end 

和一些检查，它的工作原理：

 >> common %w{ interspecies interstelar interstate } => "inters" >> common %w{ dog dalmation } => "d" >> common %w{ asdf qwerty } => "" >> common ['', 'asdf'] => "" 

Answer 24

有趣的替代Ruby解决scheme

 def common_prefix(*strings) chars = strings.map(&:chars) length = chars.first.zip( *chars[1..-1] ).index{ |a| a.uniq.length>1 } strings.first[0,length] end p common_prefix( 'foon', 'foost', 'forlorn' ) #=> "fo" p common_prefix( 'foost', 'foobar', 'foon' ) #=> "foo" p common_prefix( 'a','b' ) #=> "" 

如果您使用chars = strings.sort_by(&:length).map(&:chars) ，它可能会帮助您加快速度，因为第一个string越短， zip创build的数组越短。 但是，如果您关心速度，您可能不应该使用此解决scheme。 🙂

Answer 25

JavaScript的克隆AShelly的优秀答案。

需要Array#reduce只在Firefox中支持。

 var strings = ["interspecies", "intermediate", "interrogation"] var sub = strings.reduce(function(l,r) { while(l!=r.slice(0,l.length)) { l = l.slice(0, -1); } return l; }); 

Answer 26

这绝不是优雅的，但如果你想简洁：

Ruby，71个字符

 def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end 

如果你想展开它看起来像这样：

 def f(words) first_word = words[0]; first_word[0, (0..(first_word.size)).find { |num_chars| words.any? { |word| word[0, num_chars] != first_word[0, num_chars] } } - 1] end 

Answer 27

这不是高尔夫的代码，但你要求有些优雅，我倾向于认为recursion是有趣的。 Java的。

 /** Recursively find the common prefix. */ public String findCommonPrefix(String[] strings) { int minLength = findMinLength(strings); if (isFirstCharacterSame(strings)) { return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings)); } else { return ""; } } /** Get the minimum length of a string in strings[]. */ private int findMinLength(final String[] strings) { int length = strings[0].size(); for (String string : strings) { if (string.size() < length) { length = string.size(); } } return length; } /** Compare the first character of all strings. */ private boolean isFirstCharacterSame(String[] strings) { char c = string[0].charAt(0); for (String string : strings) { if (c != string.charAt(0)) return false; } return true; } /** Remove the first character of each string in the array, and return a new array with the results. */ private String[] removeFirstCharacter(String[] source) { String[] result = new String[source.length]; for (int i=0; i<result.length; i++) { result[i] = source[i].substring(1); } return result; } 

Answer 28

基于@ Svantealgorithm的ruby版本。 运行速度与我的第一个相同。

  def common_prefix set i=0 rest=set[1..-1] set[0].each_byte{|c| rest.each{|e|return set[0][0...i] if e[i]!=c} i+=1 } set end 

Answer 29

我的Javascript解决scheme：

IMOP，使用sorting太棘手。 我的解决scheme是通过循环数组来比较字母。 如果字母不是嵌套的，则返回string。

这是我的解决scheme：

 var longestCommonPrefix = function(strs){ if(strs.length < 1){ return ''; } var p = 0, i = 0, c = strs[0][0]; while(p < strs[i].length && strs[i][p] === c){ i++; if(i === strs.length){ i = 0; p++; c = strs[0][p]; } } return strs[0].substr(0, p); }; 

Answer 30

意识到这样的风险转化为代码高尔夫 （或者是意图？）的匹配，这里是我使用sed的解决scheme，从我的答案复制到另一个SO问题并缩短为36个字符（其中30个是实际的sedexpression式） 。 它期望string（每个单独的行）在标准input或作为附加parameter passing的文件中提供。

 sed 'N;s/^\(.*\).*\n\1.*$/\1\n\1/;D' 

seb在shebang线脚本重量在45个字符：

 #!/bin/sed -f N;s/^\(.*\).*\n\1.*$/\1\n\1/;D 

脚本的testing运行（名为longestprefix ），string作为“here文档”提供：

 $ ./longestprefix <<EOF > interspecies > interstelar > interstate > EOF inters $