적절한 시간 내에 문자열을 비교하는 더 좋은 방법이 있습니까?

Question

두 개의 문자열이 "거의"같다면, 즉 문자열의 모든 문자가 동일하고 하나를 제외하고 같은 방식으로 정렬 된 경우이 루비 함수가 있습니다. 그래서 예를 들어, 이러한

equal 
eual 

동일하지만, 이러한이되지

eal 
equal 

(두 글자 위의 누락). 도움, 나는이

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

와 함께 올라와있다 그래서있는 라스는

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> 

21 시간 대신 1 초가 내 비교 시간을 얻을 수있는 곳이 있습니까?

Answer 1

시도해보십시오. 주된 아이디어는 방법이 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