上一篇:2. 两数相加(AddTwoNumbers)
题目(Medium)
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
给定一个字符串，找出不含有重复字符的 最长子串 的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
脑洞时间
这个问题是不是有点像数组求最大值的问题,我们需要遍历数组,挨个比较然后给最大值不断赋值,直到最后遍历完毕找到最大值.这里不一样的地方是求最长无重复子串,重点在无重复三字.
遍历目标字符串,用一个字符串变量拼接并缓存遍历过的字符,当遇到一个字符包含于缓存字符串时需要以首个重复字符后一位开始重新开始找新子串.eg:
"pwabwkw",当遍历到第二个'w'时,缓存字符串为"pwab",w重复
此时需要从首个重复字符'w'后一位'a'开始继续找,即该次缓冲字符串为"ab",参与下次拼接"abw"形成新的缓冲字符串..."abwk"为最终的最长不重复子串.
此外,这个问题还要考虑到某些特殊情况:
1.目标字符串为单个字符时:"a"
2.目标字符串为单个字符重复:"aaaaaaa"
3. 当前最长子串与最长子串的赋值时机:
我们知道当遇到重复子串时需要比较当前最长子串与最长子串长度,以对最长子串进行赋值.
但是如果最后一次遍历时没有重复子串,且最后一次形成的当前最长子串比最长子串长,这样就没有进行这次的比较赋值导致结果错误.
所以,在遍历完毕后还要判断一下当最长子串是否比当前最长子串长.(当然,这个点主要针对我的算法思路)
->>
废话少说撸代码
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 最长子串
rs = ""
# 当前最长子串
cur_rs = ""
for i in s:
if i in cur_rs:
# 最长串赋值
if len(cur_rs) > len(rs):
rs = cur_rs
# 去掉重复字符的当前最长串
index = cur_rs.index(i)
cur_rs = cur_rs[index+1:]
cur_rs += i
# 判断一下当最长子串是否比当前最长子串长
rtype = len(rs)
if len(rs) < len(cur_rs):
rtype = len(cur_rs)
return rtype
def main():
# 自定义测试用例
r = Solution().lengthOfLongestSubstring("eeydgwdykpv")
print(r)
if __name__ == '__main__':
main()
算法复杂度
时间复杂度为:O(N)，N为目标字符串长度
空间复杂度为:O(N), N为目标字符串长度
->
->
->
->
下一篇:4.两个排序数组的中位数(MedianofTwoSortedArrays)
->
->
------------------------------20180312夜
刷Leetcode，
在我看来，
其实是为了维持一种编程状态！
