LeetCode--无重复最长子串(python版)

2018-12-21  本文已影响0人  猫爱吃草莓
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        unique_str=set()
        max_length,i,j=0,0,0
        n=len(s)
        while (i<n and j<n):
            if s[j] not in unique_str:
                unique_str.add(s[j])
                j=j+1
                max_length=max(j-i,max_length)
            else:
                unique_str.remove(s[i])
                i=i+1
        return max_length

重点:

1、使用set作为无重复的集合

2、制作滑动窗口--两个指针从头到尾遍历字符串

解法二(动态规划法):

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict1={}
        max_length,i=0,0
        for index,value in enumerate(s):
            if dict1.has_key(value):
                i=max(dict1[value]+1,i)
            dict1[value]=index
            max_length=max(max_length,index-i+1)
        return max_length

重点:
1、使用哈希
2、注意下标边界
3、i=max(dict1[value]+1,i),i要一直向前移动

上一篇 下一篇

猜你喜欢

热点阅读