重複のない最長部分文字列の検索 - コードの最適化のヘルプ [Ruby]

概要

そこで私は Leetcode の質問、「文字列が与えられた場合、文字を繰り返さずに最も長い部分文字列の長さを見つけてください」を解決しようとしています。

例えば

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

現在、ハッシュテーブルを使用して部分文字列が一意であるかどうかを判断するアルゴリズムを最適化しています。ただし、コードは依然として O(n^2) ランタイムで実行され、その結果、送信中に制限時間を超えてしまいます。

私がやろうとしているのは、基本的に考えられるすべての部分文字列を調べて、重複する値があるかどうかを確認することです。ここで強引な方法を実行する場合、私はこれほど効率的でしょうか?スライディングウィンドウ法などの他の方法があることは知っていますが、最初に総当たり法を理解しようとしています。

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    max_length = 0
    max_string = ""
    n = s.length
    for i in (0..n-1)
        for j in (i..n-1)
            substring = s[i..j]
            #puts substring
            if unique(substring)
                if substring.length > max_length
                    max_length = substring.length
                    max_string = substring
                end
            end
        end
    end
    return max_length
end

def unique(string)
    hash = Hash.new(false)
    array = string.split('')
    array.each do |char|
        if hash[char] == true
            return false
        else
            hash[char] = true
        end
    end
    return true
end

解決策

アプローチ

ここでは、文字をインデックスにマッピングするハッシュを使用してこれを行う方法を示します。文字列 s の場合、部分文字列 s[j..j+n-1] 内の文字が一意であるため、その部分文字列が最長の一意の部分文字列の候補であるとします。したがって、次の要素は e = s[j+n] です。 s[j..j+n-1] に e が含まれるかどうかを判断したいとします。そうでない場合は、部分文字列に e を追加して、一意性を保つことができます。

s[j..j+n-1] に e が含まれる場合、n (部分文字列のサイズ) が既知の部分文字列の長さより大きいかどうかを判断し、大きい場合はレコードを更新します。 s[j..j+n-1] に e が含まれるかどうかを判断するには、部分文字列の線形検索を実行できますが、キーと値のペアが s[i]=>i であるハッシュ c_to_i を維持する方が高速です。 i = j..j_n-1。つまり、 c_to_i は部分文字列内の文字を完全な文字列内のインデックスにマップします。そうすれば、単に c_to_i.key?(e) を評価して、部分文字列に e が含まれているかどうかを確認できます。部分文字列に e が含まれる場合、c_to_i を使用して s 内のインデックスを決定し、1 を追加します: j = c_to_i[e] + 1。したがって、新しい部分文字列は、j の新しい値を持つ s[j..j+n-1] になります。。このステップでは、s のいくつかの文字がスキップされる場合があることに注意してください。

部分文字列に e が含まれているかどうかに関係なく、(おそらく更新された) 部分文字列に e を追加して、s[j..j+n] にする必要があります。

コード

def longest_no_repeats(str)
  c_to_i = {}
  longest = { length: 0, end: nil }
  str.each_char.with_index do |c,i|
    j = c_to_i[c]
    if j
      longest = { length: c_to_i.size, end: i-1 } if
        c_to_i.size > longest[:length]
      c_to_i.reject! { |_,k| k <= j }
    end
    c_to_i[c] = i
  end
  c_to_i.size > longest[:length] ? { length: c_to_i.size, end: str.size-1 } :
    longest
end

例

a = ('a'..'z').to_a
  #=> ["a", "b",..., "z"]

str = 60.times.map { a.sample }.join
  #=> "ekgdaxxzlwbxixhlfbpziswcoelplhobivoygmupdaexssbuuawxmhprkfms"

longest = longest_no_repeats(str)
  #=> {:length=>14, :end=>44} 
str[0..longest[:end]]
  #=> "ekgdaxxzlwbxixhlfbpziswcoelplhobivoygmupdaexs" 
str[longest[:end]-longest[:length]+1,longest[:length]]
  #=>                                "bivoygmupdaexs"

効率

@mechnicov のコードとのベンチマーク比較は次のとおりです。

require 'benchmark/ips'

a = ('a'..'z').to_a
arr = 50.times.map { 1000.times.map { a.sample }.join }

Benchmark.ips do |x|
  x.report("mechnicov") { arr.sum { |s| max_non_repeated(s)[:length]   } }
  x.report("cary")      { arr.sum { |s| longest_no_repeats(s)[:length] } }
  x.compare!
end

表示:

Comparison:
            cary:       35.8 i/s
       mechnicov:        0.0 i/s - 1198.21x  slower