【leedcode】0003. 无重复字符最长子串

x33g5p2x  于2021-11-09 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(77)

【leedcode】0003. 无重复字符最长子串

给定一个字符串,请你找出其中不含有重复字符的 **最长子串 **的长度。
示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是 子串的长度,"wke" 是一个子序列,不是子串长度。

方法一:

def maxSizeSubstring(s):
    res,cur,dic = 0,0,{}
    for idx in range(len(s)):
        if s[idx] in dic:
            cur = max(cur, dic[s[idx]] + 1)
        dic[s[idx]] = idx
        res = max(res, idx - cur + 1)      
    return res

sample = "abcabcbb","bbbbb","pwwkew","I am HannYang."

for s in sample:
    print(maxSizeSubstring(s))

方法二:


 

def maxSizeSubstring2(s):
    res = 0
    for i in range(len(s)):
        for j in range(len(s),0,-1):
            if i>=j: continue
            t = s[i:j]
            size = len(t)
            if size==len(set(t)):
                if size>res:
                    res = size
    return res

sample = "abcabcbb","bbbbb","pwwkew","I am HannYang."

for s in sample:
    print(maxSizeSubstring2(s))

方法三:

Max = lambda s: max([len(s[i:j]) for i in range(len(s)) for j in range(i+1,len(s)+1) if len(s[i:j])==len(set(s[i:j]))])

sample = "abcabcbb","bbbbb","pwwkew","I am HannYang."

for s in sample:
    print(Max(s))

以上三种方法的运行结果都是:

3
1
3
5

其中,方法三只是把方法二改造成了一行代码的lambda表达式。

欢迎加入“派森特给站”社区!

https://bbs.csdn.net/forums/PythonTogether

相关文章

微信公众号

最新文章

更多