Ruby - 删除字符串？

Question

问题：给定两个字符串X和Y， 找到要从X中移除的最少字符数，以获得不包含Y作为子字符串的字符串X'。

输入：ababba ABA

预期输出：1（输出恰好一个整数将被去除的字符的最小数目）我已经简单地完成串是否是

我的代码是否存在或不存在

str1 = gets.chomp 
str2 = gets.chomp 
if str1.include? str2 
    puts "yup" 
else 
    puts "no" 
end 

Answer 1

没有效率关注的直接解决方案：

def remove_count(x, y) 
    index = x.index(y) 
    if index.nil? 
    0 
    else 
    removes = [] 
    index.upto(index + y.length - 1) do |i| 
     r = remove_count(x[0, i] + x[(i+1)..-1], y) 
     if r == 0 
     return 1 
     else 
     removes << r 
     end 
    end 
    removes.min + 1 
    end 
end 

puts remove_count('ababba', 'aba') 
puts remove_count('aaaaaa', 'aa') 

BTW：我对高效解决方案感兴趣。我认为这应该被标记为algorithm。