LeetCode 003 無重複字元的最長子串

2022-09-22 06:02:07 字數 2556 閱讀 1192

問題描述:

給定一個字串,找出不含有重複字元的最長子串的長度。

示例 1:

輸入:"abcabcbb"輸出:3解釋:無重複字元的最長子串是"abc",其長度為 3。
示例 2:

輸入:"bbbbb"輸出:1解釋:無重複字元的最長子串是"b",其長度為 1。
示例 3:

輸入:"pwwkew"輸出:3解釋:無重複字元的最長子串是"wke",其長度為 3。

請注意,答案必須是一個子串"pwke"是一個子序列 而不是子串。

學業繁重,沒時間寫了。。。。。。

方法1:s="pwwkew"  d={} () ,當s[i]在d中,start=d[s[i]] + 1從下一個位置開始,temp 儲存最大長度 temp=max(i-start+1,temp)

1

class

solution:

2def

lengthoflongestsubstring(self, s):

3"""

4:type s: str

5:rtype: int

6"""

7 d={}

8 start =0

9 temp =0

10for i in

range(len(s)):

11if s[i] in d and start <=d[s[i]]:

12 start = d[s[i]] + 1

13 temp = max(temp,i-start+1)

14 d[s[i]] =i

15return

temp

16

方法2:

1

class

solution:

2def

lengthoflongestsubstring(self, s):

3"""

4:type s: str

5:rtype: int

6"""

7 sub=''

8 sub_len=0

9 max_len=0

10 max_sub=''

11for letter in

s:12

if letter in

sub:

13if sub_len>max_len:

14 max_len=sub_len

15 max_sub=sub

16 index=sub.index(letter)

17 sub=sub[index+1:]+letter

18 sub_len=sub_len-index

19else

:20 sub=sub+letter

21 sub_len+=1

22if sub_len>max_len:

23 max_len=sub_len

24return max_len

方法3:

1

class

solution:

2def

lengthoflongestsubstring(self, s):

3"""

4:type s: str

5:rtype: int

6"""

7 start = max_len =0

8 used ={}910

for i in

range(len(s)):

11if s[i] in used and start <=used[s[i]]:

12 start = used[s[i]] + 1

13else

:14 max_len = max(max_len, i - start + 1)

15 used[s[i]] =i

1617

return max_len

2018-10-15 22:43:21