有没有更好的方法在合理的时间内比较字符串?

Is there a better way to compare strings in a reasonable amount of time?

我有这个 Ruby 函数,它告诉我两个字符串是否 "almost" 相等,也就是说,字符串中的所有字符是否相同并且以相同的方式排序,除了一个。例如,这些是相等的

equal
eual

但这些不是

eal
equal

(上面少了两个字符)。所以在帮助下,我想出了这个

(lcs(a,b) == shortest && longest.length - shortest.length == 1)

其中las由

定义
  def lcs(xstr, ystr)
    return "" if xstr.empty? || ystr.empty?

    x, xs, y, ys = xstr[0..0], xstr[1..-1], ystr[0..0], ystr[1..-1]
    if x == y
      x + lcs(xs, ys)
    else
      [lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
    end
  end

但是我的功能花费了非常长的时间。注意下面我的基准

2.4.0 :011 > timing = Benchmark.measure { StringHelper.lcs("navesxkolsky|1227000", "navsxkolsky|1227000") }
 => #<Benchmark::Tms:0x007fa1753830d8 @label="", @real=21.341279999993276, @cstime=0.0, @cutime=0.0, @stime=0.030000000000000027, @utime=21.28, @total=21.310000000000002>

这里有什么我遗漏的东西可以让我的比较时间缩短到 1 秒而不是 21 秒吗?

试试这个。主要思想是,如果该方法是 return false,它会在已知时立即这样做,即使需要冗余代码也是如此。 (如果删除行 return false if (sz1-sz2).abs > 1,下面的方法仍然有效。)

def equal_but_one?(str1, str2)
  sz1 = str1.size
  sz2 = str2.size
  return false if (sz1-sz2).abs > 1
  i = [sz1, sz2].max.times.find { |i| str1[i] != str2[i] }
  return false if i.nil?
  case sz1 <=> sz2
  when 0
    str1[i+1..-1] == str2[i+1..-1]
  when -1
    str2[i+1..-1] == str1[i..-1]
  when 1
    str1[i+1..-1] == str2[i..-1]
  end
end

equal_but_one?('cat', 'cut')     #=> true
equal_but_one?('bates', 'bats')  #=> true
equal_but_one?('buss', 'bus')    #=> true
equal_but_one?('cat', 'cat')     #=> false
equal_but_one?('pig', 'pigs')    #=> true 
equal_but_one?('pig', 'pegs')    #=> false
equal_but_one?('', '')           #=> false
equal_but_one?('', 'a')          #=> true

require 'benchmark'

Benchmark.measure { equal_but_one?("navesxkolsky|1227000", "navsxkolsky|1227000") }.real
  #=> 1.6000005416572094e-05