在字符串数组中查找公共字符串（ruby）
鉴于我有一个3个字符串的数组：
["Extra tv in bedroom", "Extra tv in living room", "Extra tv outside the shop"] 如何找到所有字符串共有的最长字符串？
这是一种ruby的做法。 如果您有一堆字符串或者它们很长，您应该使用更高级的算法：
def longest_common_substr(strings) shortest = strings.min_by &:length maxlen = shortest.length maxlen.downto(0) do |len| 0.upto(maxlen - len) do |start| substr = shortest[start,len] return substr if strings.all?{|str| str.include? substr } end end end puts longest_common_substr(["Extra tv in bedroom", "Extra tv in living room", "Extra tv outside the shop"])
这篇维基百科文章介绍了可用于解决该问题的两种算法。
如果要搜索所有字符串的开头：
资源
def substr( a ) return "" unless (a.length > 0) result = 0 (0 ... a.first.length).each do |k| all_matched = true character = a.first[k] a.each{ |str| all_matched &= (character == str[k]) } break unless all_matched result+=1 end a.first.slice(0,result) end
测试
input = ["Extra tv in bedroom", "Extra tv in living room", "Extra tv outside the shop"] puts substr( input ) + "."
产量
Extra tv .
也仅适用于字符串的开头。
def longest_subsequence array array.sort! first = array[0].split(//) last = array[-1].split(//) length = (first.size > last.size) ? last.size : first.size sequence = "" index = 0 while (first[index] == last[index]) && (index < length) sequence << first[index] index += 1 end sequence end
但是我认为应该有一种方法可以轻松地比较匹配子字符串的两个字符串的开头 - 我现在就想不到它！
不要认为这个特别好。
def longest_substr(text) if (text.length == 0) return "" elseIf (text.length == 1) return text[0] end longest = text.inject(text[0].length) {|min, s| min < s.length ? min : s.length} (1 .. longest).to_a.reverse.each do |l| (0 .. text[0].length - l).each do |offset| str = text[0].slice(offset, l) matched = (1 .. text.length - 1).inject(true) {|matched, i| matched && text[i].index(str) != nil} if (matched) return str end end end return "" end puts longest_substr(["Alice's Extra tv in bedroom", "Bob's Extra tv in living room", "My Extra tv outside the shop"])
不知道响应是否仍然有用，但这是一个受@ mckeed和@ lins314159代码启发的解决方案。
def longest_common_substr(strings) longest_substring = strings.map{|s| s.split}.max_by &:length longest_substring.inject do |target_str, token| r = Regexp.new("^#{target_str.nil? ? token : "#{target_str} #{token}".strip}") target_str = "#{target_str} #{token}".strip if strings.all? {|string| string =~ r} target_str end end puts longest_common_substr(["Extra tv and mat in bedroom", "Extra tv and chair with view in living room", "Extra tv and carpet outside the shop"])