# 瞎扯淡 被一道 leetcode 中等题难住了

lyb124553153 · 2022年06月30日 · 最后由 xerox51 回复于 2023年12月24日 · 1022 次阅读

``````def maximum_removals(s, tp, removable)
left = 0
@m = s.size
@n = tp.size
right = [removable.size(),@m - @n].min
while left < right
mid = (right - left + 1) / 2 + left
if can_remove?(s,tp,removable, mid)
left = mid
else
right = mid - 1
end
end

left
end

def can_remove?(s, tp, removable, k)
r = []
(0...k).each do |i|
r[removable[i]] = true
end
i = 0
j = 0

while i < @m do
if s[i] == tp[j] && !r[i]
j += 1
return true if j == @n
end
i += 1
end

false
end
``````

ruby 做算法题在耗时上有劣势。同样的算法用其他语言写可以过。

``````def maximum_removals(s, p, removable)
@m = s.length
@n = p.length
left = 0
right = [removable.length, @m - @n].min
while left < right
mid = (right - left + 1) / 2 + left
temp = (removable[0, mid]).to_h {|item| [item,true]}
if judge(s, p, temp)
left = mid
else
right = mid - 1
end
end
return left
end

def judge(s, p, r)
j = 0
i = 0
while i < @m
unless r[i]
if s[i] == p[j]
j += 1
if j == @n
return true
end
end
end
i += 1
end
return false
end
``````

lithium4010 回复

``````def maximum_removals(s, t, a)
s, t = [s, t].map! { _1.each_char.map(&:ord) }
r, iz, jz = 0, s.size, t.size
(1..[iz - jz, a.size].min).bsearch do |k|
c = s.clone
(0...k).each { c[a[_1]] = 0 }
i = j = 0
while j < jz
i += 1 while i < iz && c[i] != t[j]
break if i == iz
i += 1
j += 1
end
j == jz ? (r = k if k > r; 1) : -1
end
r
end
``````