Leetcode

[leetcode]3.无重复字符的最长子串

2019-01-09  本文已影响0人  LeeYunFeng

题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

解题思路:

  1. 最初的思路是采用笨办法,也就是暴力的列出所有子串,判断各个子串是否满足“不含重复字符”的条件,如果满足则记录字符串长度。从最长的子串开始搜索,一旦出现满足条件的子串,就返回结果。
    采用以上方法的时间复杂度为O(n^3),最终在某些测试样例上运行超时。

  2. 借鉴其它的思路,可以只遍历一次字符串的各个字符,记录当前最长子串的长度,同时记录当前子串的起始位置,遍历完成后即可得最终结果。使用这种方法时,不仅要用到各个字符的value,还需要用到对应的index,充分用到所有相关信息。时间复杂度为O(n)。

笨办法:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n=len(s)
        if n==0:
            return 0
        for l in range(n,0,-1):
            for i in range(0,n-l+1,1):
                d={}
                for j in s[i:i+l]:
                    if d.get(j):
                        d[j]+=1
                    else:
                        d[j]=1
                if max(d.values())==1:
                    return l

更快速的方法:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start=0#当前子串的起始位置
        lmax=0#当前最大的子串长度
        d={}#用于记录value和index之间的映射
        for i,v in enumerate(s):
            # v in d表示此前出现过相同的字符,需要重新指定start
            if v in d:
                start=max(d[v]+1,start)
            # 记录当前各个字符对应的最大index
            d[v]=i
            # 得到当前最大的子串长度
            lmax=max(lmax,i-start+1)
        return lmax
上一篇下一篇

猜你喜欢

热点阅读