查找一组字符串中最长的公共起始子字符串 [英] Find the longest common starting substring in a set of strings
问题描述
这个问题是一个比较特殊的情况， 最长的常见子字符串问题。我只需要在数组中找到最长的公共起始子字符串。这极大地简化了问题。例如， [interspecies，interstelar，interstate] 中最长的子字符串是半成品。然而，我不需要在 [特定的，很棒的] 中找到定义。
我已经通过在JavaScript中快速编写解决方案来解决问题，作为我的一部分关于shell-like tab-completion 的答案（测试页面在这里）。以下是该解决方案，稍作调整：
函数common_substring（data）{
var i，ch，memo，idx = 0
do {
memo = null
for（i = 0; i
else if（ch！= memo）break
}
} data.length& idx< data.length&& ++ idx）
return（data [0] ||''）.slice（0，idx）
} b
$ b =nofollow noreferrer>代码在这个Gist中可用以及Ruby中的类似解决方案。您可以将gist克隆为git repo来体验它：
$ git clone git：//gist.github.com /257891.git子串挑战
我对这些解决方案并不满意。我有一种感觉，他们可以用更多的优雅和更少的执行复杂性来解决 - 这就是为什么我发布这个挑战。
我会接受作为答案的解决方案我觉得最优雅或简洁。例如，我想出了一个疯狂的Ruby黑客 - 在字符串中定义& 运算符：
＃与Ruby 1.8.7及以上版本兼容
class String
def&（other）
difference = other.to_str.each_char.with_index.find {| ch，idx |
self [idx] .nil？或ch！= self [idx] .chr
}
差异？ self [0，difference.last]：self
end
end
class Array
def common_substring
self.inject（nil）{| memo，海峡| memo.nil？ ？ str：备忘录& str} .to_s
end
end
JavaScript或Ruby的解决方案是首选，但只要你解释发生了什么，你可以在其他语言中展示聪明的解决方案。请仅使用标准库中的代码。
更新：我最喜欢的解决方案
我选择了 JavaScript排序解决方案 其他很棒的解决方案：
- 。 Yehuda Katz也制作了正则表达式解决方案，但它更复杂
-
commonprefix in Python - Roberto Bonvallet使用了一个用于处理文件系统路径的功能来解决这个问题。 =/ questions / 1916218 / find-the-longest-common-starting-substring-in-a-set-of-strings / 1918438＃1918438> Haskell one-liner 很短，就好像它被压缩一样，和美丽
- 直接的Ruby单线程
感谢您的参与！正如你从评论中看到的，我学到了很多东西（甚至是关于Ruby的）。
这是一个品味的问题，但这是一个简单的javascript版本：
它对数组进行排序，然后看第一个和最后一个项目。
//最长公共起始子字符串array
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 ++;
返回a1.substring（0，i）;
}
DEMOS $ b
sharedStart（['interspecies'，'interstelar'，'interstate']）// => 'inters'
sharedStart（['throne'，'throne']）// => 'throne'
sharedStart（['throne'，'dungeon']）// => ''
sharedStart（['cheese']）// => 'cheese'
sharedStart（[]）// => ''
sharedStart（['prefix'，'suffix']）// => ''
This is a challenge to come up with the most elegant JavaScript, Ruby or other solution to a relatively trivial problem.
This problem is a more specific case of the Longest common substring problem. I need to only find the longest common starting substring in an array. This greatly simplifies the problem.
For example, the longest substring in [interspecies, interstelar, interstate] is "inters". However, I don't need to find "ific" in [specifics, terrific].
I've solved the problem by quickly coding up a solution in JavaScript as a part of my answer about shell-like tab-completion (test page here). Here is that solution, slightly tweaked:
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)
}
This code is available in this Gist along with a similar solution in Ruby. You can clone the gist as a git repo to try it out:
$ git clone git://gist.github.com/257891.git substring-challenge
I'm not very happy with those solutions. I have a feeling they might be solved with more elegance and less execution complexity—that's why I'm posting this challenge.
I'm going to accept as an answer the solution I find the most elegant or concise. Here is for instance a crazy Ruby hack I come up with—defining the & operator on 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
Solutions in JavaScript or Ruby are preferred, but you can show off clever solution in other languages as long as you explain what's going on. Only code from standard library please.
Update: my favorite solutions
I've chosen the JavaScript sorting solution by kennebec as the "answer" because it struck me as both unexpected and genius. If we disregard the complexity of actual sorting (let's imagine it's infinitely optimized by the language implementation), the complexity of the solution is just comparing two strings.
Other great solutions:
- "regex greed" by FM takes a minute or two to grasp, but then the elegance of it hits you. Yehuda Katz also made a regex solution, but it's more complex
commonprefix in Python — Roberto Bonvallet used a feature made for handling filesystem paths to solve this problem- Haskell one-liner is short as if it were compressed, and beautiful
- the straightforward Ruby one-liner
Thanks for participating! As you can see from the comments, I learned a lot (even about Ruby).
解决方案 It's a matter of taste, but this is a simple javascript version:
It sorts the array, and then looks just at the first and last items.
//longest common starting substring in an array
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']) //=> ''
这篇关于查找一组字符串中最长的公共起始子字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
