leetcode algorithm3 Substring Without Repeating Characters

leetcode algorithm3 Substring Without Repeating Characters
原題リンク
に質問
Given a string, find the length of the longest substring without repeating characters. Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
構想
まず力の方法を話します.bufferを探して、スキャンの順序で文字列の中の要素を順番にbufferに加えて、もし次の要素がすでにbufferの中に入っているならば、bufferを短縮して、KMPのように、ただ私達はただ1回だけ短縮して、私達はずっとbufferの中で繰り返しの要素を含まないことを保証しますためです.短縮する方法は、重複する要素が現れた場所とその前の部分を捨てることです.次の文字列の要素を追加します.max変数を同時に維持します.
時間の複雑さを分析します.外層サイクルコストO(n)として文字列をスキャンする.bufferに要素を追加するたびに、bufferに要素が存在するかどうかを確認します.線形検査であればO(n),HashであればO(1),秩序構造であればO(logn)である.問題は、見つかった最大重複しない文字列を秩序正しく返す必要がないため、順序を維持する必要はありません.ここではbufferとしてhashmapを選んだほうがいいです.要素をキーとし、indexを値とします.
もちろんsetでこのスライドウィンドウをメンテナンスすることもできますが、removeが要素を落とすたびに前からremoveが1つずつ落ちて重複要素がまだあるかどうかを見るしかありません.
コード#コード#
python実装,ここではbuffer用配列とmapによる実装方式を示した

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        current = ""
        max = 0
        for i in range(len(s)): # range start from 0
            # if there is a existing character
            if s[i] in current:
                # we cut a part of the current to continue
                index = current.find(s[i])

                # handle the boundary value
                if index+1 < len(current):
                    current = current[index+1:]
                    current += s[i]
                else:
                    current = s[i]
            # if the character not in there, just add it to the buffer
            else:
                current += s[i]
                if len(current) > max:
                    max = len(current)
        return max

    def lengthOfLongestSubstringBetter(self, s):
        """
        :type s: str
        :rtype: int
        """
        current = {}
        left_boundary = 0
        max = 0
        for i in range(len(s)): # range start from 0
            #if current.has_key(s[i]):
            # the above function is for python 2.X, the latter is for python 3.X
            if current.__contains__(s[i]):
                # we update the length
                index = current[s[i]]
                if left_boundary <= index:
                    left_boundary = index + 1

            current[s[i]] = i
            length = i - left_boundary + 1
            if length > max:
                max = length

        return max

instance = Solution()
str = "tmmzuxt"
print(instance.lengthOfLongestSubstring(str))
print(instance.lengthOfLongestSubstringBetter(str))
str = "aab"
print(instance.lengthOfLongestSubstring(str))
print(instance.lengthOfLongestSubstringBetter(str))