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。