查找最长子字符串且无重复-帮助优化代码[Ruby] [英] Finding Longest Substring No Duplicates - Help Optimizing Code [Ruby]
问题描述
所以我一直在尝试解决密码问题,给出一个字符串,找到最长的子字符串的长度而不重复字符."
So I've been trying to solve a Leetcode Question, "Given a string, find the length of the longest substring without repeating characters."
例如
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
当前,我在使用哈希表确定子字符串是否唯一时优化了我的算法.但是我的代码仍在O(n ^ 2)运行时中运行,结果超过了提交期间的时间限制.
Currently I optimized my algorithm when it comes to figuring out if the substring is unique by using a hash table. However my code still runs in O(n^2) runtime, and as a result exceeds the time limit during submissions.
我想做的基本上是遍历每个可能的子字符串,并检查它是否有重复的值.在这里使用蛮力方法时,我是否高效?我知道还有其他方法,例如滑动窗口方法,但我正在尝试首先降低蛮力方法.
What i try to do is to essentially go through every single possible substring and check if it has any duplicate values. Am I as efficient as it gets when it comes to the brute force method here? I know there's other methods such as a sliding window method but I'm trying to get the brute force method down first.
# @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
附加到子字符串,使其保持唯一.
Here is a way of doing that with a hash that maps characters to indices. For a string s
, suppose the characters in the substring s[j..j+n-1]
are unique, and therefore the substring is a candidate for the longest unique substring. The next element is therefore e = s[j+n]
We wish to determine if s[j..j+n-1]
includes e
. If it does not we can append e
to the substring, keeping it unique.
如果s[j..j+n-1]
包括e
,我们将确定n
(子字符串的大小)是否大于先前已知的子字符串的长度,如果是,则更新我们的记录.要确定s[j..j+n-1]
是否包括e
,我们可以对子字符串执行线性搜索,但是维护键值对为s[i]=>i
,i = j..j_n-1
的哈希c_to_i
更快.也就是说,c_to_i
将子字符串中的字符映射到其完整字符串s
中的索引.这样,我们只能评估c_to_i.key?(e)
来查看子字符串是否包含e
.如果子字符串包含e
,则使用c_to_i
确定其在s
中的索引并添加一个:j = c_to_i[e] + 1
.因此,新的子字符串为s[j..j+n-1]
,其新值为j
.请注意,在此步骤中可能会跳过s
的几个字符.
If s[j..j+n-1]
includes e
, we determine if n
(the size of the substring) is greater than the length of the previously-known substring, and update our records if it is. To determine if s[j..j+n-1]
includes e
, we could perform a linear search of the substring, but it is faster to maintain a hash c_to_i
whose key-value pairs are s[i]=>i
, i = j..j_n-1
. That is, c_to_i
maps the characters in the substring to their indices in full string s
. That way we can merely evaluate c_to_i.key?(e)
to see if the substring contains e
. If the substring includes e
, we use c_to_i
to determine its index in s
and add one: j = c_to_i[e] + 1
. The new substring is therefore s[j..j+n-1]
with the new value of j
. Note that several characters of s
may be skipped in this step.
无论子字符串是否包含e
,现在我们都必须将e
附加到(可能已更新的)子字符串上,以使其变为s[j..j+n]
.
Regardless of whether the substring contained e
, we must now append e
to the (possibly-updated) substring, so that it becomes 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代码的基准比较:
Here is a benchmark comparison to @mechnicov's code:
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
这篇关于查找最长子字符串且无重复-帮助优化代码[Ruby]的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!