查找一组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)。

这是一个味道的问题,但这是一个简单的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']) //=> '' 

在Python中:

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

ruby单行:

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

我的Haskell单行:

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

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

你只需要遍历所有的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)))) 

还有另一种方法:使用正则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] 

在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

这可能不是最简洁的解决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

只是为了它的乐趣,这是用(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附加到结果,否则结束。

干净,简单,高效… 🙂

基于@ 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; } 

结合kennebecFlorian Fjberryman的答案可以得出以下Haskell单行:

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

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

 commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum) 
 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 

如果你不是太在意最终的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 

这个和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"], ...

mapuniq减less到[["i"],["n"],["t"], ...

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

被接受的解决scheme被破坏了(例如,它返回a['a', 'ba']string)。 修复非常简单,你只需要改变3个字符(从indexOf(tem1) == -1indexOf(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,然后获取数组的第一个和最后一个元素。

在阅读这些答案的时候,所有的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

以下是在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 

我会做以下几点:

  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; } } } 

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

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

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

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

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

我在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); } 

高尔夫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; }); 

这是一个有效的解决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'] => "" 

有趣的替代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。 🙂

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; }); 

这绝不是优雅的,但如果你想简洁:

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 

这不是高尔夫的代码,但你要求有些优雅,我倾向于认为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; } 

基于@ 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 

我的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); }; 

意识到这样的风险转化为代码高尔夫 (或者是意图?)的匹配,这里是我使用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 $ 
Interesting Posts