402v

最近在刷leetcode，对自己的算法思路做个简单的记录，希望最后回顾起来自己是有提高的。

通篇算法都是用Ruby语言实现，文内不再赘述。Markdown没有支持数学格式，所以时间复杂度的记法比较粗糙，见谅。

这一系列的文章可以在这里找到。

本期题目:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题目难度: 中等

题意很好理解，在一个给定字符串中找到最长的、没有重复字符的子串，最后返回子串长度。

假定一组用于测试的输入：

abcabcbb

这样的最长子串是abc，期望的输出是

3

#多些时间可以少些Code 显然这是一道算法题，思考了一下发现自己知道字符串匹配算法好枯竭，能想到的只有栈、Hash、递归查找。

第一个思路是这样：从第一个字符循环查找，

substart记录当前子串开始位置，
subend记录当前子串结束位置，
substr记录子串
substr_list记录已查找出所有字符不重复的子串
sub_length记录目前最长子串的长度

当前字符与子串字符都不相同则子串长度加一，与其中某个字符相等则将当前子串保存到list中，从前面的相等字符的下一个位置开始记为substart，以当前查找字符的位置记为subend继续查找。

直到原字符串以substart为起始的剩余字符数量小于当前sub_length时，程序终止。

这个思路显然不是最好的，沿着这个思路写出的代码可能很冗长，不如不写。

于是Google开始搜索字符串有关的匹配算法，一眼就相中了KMP，虽然对这仨人儿一个都不认识，开始学呗。

又到了吐槽的时间。先前找了一篇讲KMP算法的文章，一坨坨公式看得我头晕眼花，链接就不贴了，真心觉得高等数学的公式用在字符串匹配这种事儿上真是大材小用了。看看这一坨：当看到归纳法三个字儿的时候我终于忍不住吐了一键盘之后果断再次Google人类语言的解释去了。

最终找到阮一峰老师这篇，看完之后醍醐灌顶、拍案叫绝啊，心想人家怎么就能把这么复杂的一个算法说的这么简单易懂！

现在来看看是否把KMP算法中的部分匹配表这个概念用来解LeetCode这道题，最后的结论是：然并卵。。。只能按照原来的思路尝试一下了。

#还是要Code

第一次的code，不出意外的Time Limit Exceeded了。

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    str_length = s.length
    substr_length = 0
    
    str_start = 0
    str_end = 1
    
    while substr_length < str_length - str_start do
        sub_str = s[str_start..str_end]
        
        if sub_str.index(s[str_end]) == nil then
            # repeating, relocate sub string
            substr_length = [substr_length, sub_str.length].max
            str_start += 1
            str_end = str_start + 1
        else                
            # not repeating, continue
            start_end += 1
        end
    end
    
    substr_length
end

尝试优化算法，点开Show Tags标签显示出HashTable、Two Pointers，上面的解决方案中时间开销过大的原因是这句：sub_str.index(s[str_end])，每次匹配是否repeating都要循环一遍sub_str，显然通过以s中的字符为key，字符的index为value的hash表就可以降低这个查找上的时间开销。

最终的code如下：

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    ans = 0 # answer
    hash = Hash.new(-1)
    
    start = 0
    
    s.length.times do |i|
        if hash[s[i]] != -1 then
            # longest
            ans = [ans, i - start].max
            
            # clear unused hash
            substr = s[start...hash[s[i]]]
            
            #puts "sub:#{substr} #{start} #{i}"
            substr.each_char do |c|
                hash[c] = -1
            end
            
            # move start
            start = hash[s[i]] + 1
        end
        
        hash[s[i]] = i
    end
    
    # deal with last sub string
    ans = [ans, s.length - start].max
end

#总结这道题对我来说简直就是灾难。。。

首先对Hash不熟悉，没有想到利用Hash降低查找的时间复杂度。其次太多没有想到或者想错的edge case，如：

每次repeating之后清空hash中多余的字符
最后一个字符子串需要在循环外处理
最后一个子串的长度

加之对ruby的语法还不够熟悉，比如：

s = "hello world"
puts s[2, 3] # llo
puts s[2..3] # ll
puts s[2...3] # l

此文为第三篇。

LeetCode实战 - Longest Substring Without Repeating Characters

评论 · 0