如何计算两个字符串共有的字符数？

Question

你如何计算两个字符串之间的字符交集？

例如(假设我们将调用一个方法String.intersection):

"abc".intersection("ab") = 2
"hello".intersection("hallo") = 4

好的,男孩和女孩,感谢您的大量反馈.更多例子:

"aaa".intersection("a") = 1
"foo".intersection("bar") = 0
"abc".intersection("bc") = 2
"abc".intersection("ac") = 2
"abba".intersection("aa") = 2

更多注释:维基百科定义交集如下:

集合A和B的交点,表示为A∩B,是一组是A和B的两个相交的成员的所有对象的{1,2,3}和{2,3,4}是集合{ 2,3}

Answer 1

使用字符串#count:

irb(main):001:0> "hello".count("hallo")
=> 4
irb(main):002:0> "abc".count("ab")
=> 2

Answer 2

这会传递您描述的所有测试用例:

class String
  def intersection(other)
    str = self.dup
    other.split(//).inject(0) do |sum, char|
      sum += 1 if str.sub!(char,'')
      sum
    end
  end
end

Answer 3

我会用以下的东西:

'abc'.split('') & 'ab'.split('') #=> ["a", "b"]
'hello'.split('') & 'yellow'.split('') #=> ["e", "l", "o"]

如果你想要一个方法来做到这一点:

class String
  def intersection(other)
    self.split('') & other.split('')
  end
end
'hello'.intersection('yellow') #=> ["e", "l", "o"]
'now is the time for all good men to come to the aid of their country'.intersection('jackdaws love my giant sphinx of quartz')
=> ["n", "o", "w", " ", "i", "s", "t", "h", "e", "m", "f", "r", "a", "l", "g", "d", "c", "u", "y"]

要获得共同的字符数,只需添加.size:

'hello'.intersection('yellow').size #=> 3

如果您想要所有匹配的常用字符的计数:

'hello'.count('hello'.intersection('yellow').join) #=> 4

传统上我们通过使用第一个字符串中的每个字符和一个计数器构建哈希来完成它,然后遍历第二个字符串,为每个公共字符递增计数器:

asdf = Hash[*'hello'.split('').map{ |s| [s, 0]}.flatten] #=> {"l"=>0, "o"=>0, "e"=>0, "h"=>0}
'yellow'.split('').each{ |s| asdf[s] += 1 if (asdf.key?(s)) }
asdf #=> {"l"=>2, "o"=>1, "e"=>1, "h"=>0}

常用字符数:

asdf.select{ |n,v| v > 0 }.size #=> 3

常见字符的数量:

asdf.values.inject(0){ |m,i| m += i } #=> 4