[LeetCode By Python] 3. Longest
2016-11-16 本文已影响172人
乐乐可爱睡觉
一、题目
Longest Substring Without Repeating Characters.png
二、解题
1)题意
- 题目的意思还是比较好理解的,输入一个字符串,找出没有重复字符的最长子串,返回其长度。
例如abcabcbb,abc为最长的无重复字符的子串,如果是abca或者bcab则出现了重复了。
2)关键点
- 子串没有重复,即子串里面没有重复的字符。
- 子串是需要连续的。
三、思考:
- 使用遍历的方式,存储最长的字符串长度在maxlength
- 使用两个下标(i、j),i从0开始,j从i+1开始,在没有重复的情况下,j每次增加1(步长为1),取出当前的标记下标的子串tempStr(从i到j、包括j),计算tempStr长度并记录到templength,与maxlength比较,大则赋值。
- (关键点)当遇到重复的时候:找到重复的位置,并把i移动到此处,j不变,然后循环继续。在python代码中,使用find是找到的tempStr的下标,要换成源字符串的下标表则需要加上原来的i的位置。
四、尝试与结果
class Solution(object):
def lengthOfLongestSubstring(self, s):
if (len(s) <= 1):
return len(s)
i = 0
j = 1
tempStr = s[0:1]
templength = 1
maxlength = 1
while (True):
c = s[j]
if (c in tempStr):
t = tempStr.find(c) + 1
i = i + t #新的i的坐标
#当下标为j时,s[i:j]这个字串是不包括j的,所以要把j+1(切片不会越界)
tempStr = s[i:j+1]
templength = len(tempStr)
if (templength > maxlength):
maxlength = templength
j = j + 1
if (j >= len(s)):
break
return maxlength
结果:AC