#3. Longest Substring Without Repeating Characters

上一篇 / 下一篇  2017-07-28 01:01:32 / 个人分类:leetcode

class Solution(object):
# 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.
def lengthOfLongestSubstring_old(self, s):
"""
:type s: str
:rtype: int
"""
string_length = len(s)
char_dict = dict()
result_dict = dict()

result_list = list()
start = 0
i = 0
while i != string_length:
if char_dict.get(s[i]):
if i not in char_dict[s[i]]:
char_dict[s[i]].append(i)

if start != i:
if s[start:i] not in result_list:
result_list.append(s[start:i])
if result_dict.get(len(s[start:i])):
if s[start:i] not in result_dict[len(s[start:i])]:
result_dict[len(s[start:i])].append(s[start:i])
else:
result_dict[len(s[start:i])] = list()
result_dict[len(s[start:i])].append(s[start:i])
else:
if s[i] not in result_list:
result_list.append(s[i])
if result_dict.get(1):
if s[i] not in result_dict[1]:
result_dict[1].append(s[i])
else:
result_dict[1] = list()
result_dict[1].append(s[i])
# nice point
start = char_dict[s[i]][-2]+1
i = start
char_dict = dict()
char_dict[s[i]] = list()
char_dict[s[i]].append(i)
else:
char_dict[s[i]] = list()
char_dict[s[i]].append(i)
i += 1

if s[start:] not in result_list:
result_list.append(s[start:])
if result_dict.get(len(s[start:])):
if s[start:] not in result_dict[len(s[start:])]:
result_dict[len(s[start:])].append(s[start:])
else:
result_dict[len(s[start:])] = list()
result_dict[len(s[start:])].append(s[start:])

# print(char_dict)
print(result_list)
print(result_dict)
if result_dict.keys():
return max(result_dict.keys())
else:
return 0

    def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
i = 0
len = 0
char_dict = dict()
for j,str1 in enumerate(s):
if str1 in char_dict.keys():
i = max(i, char_dict.get(str1, 0)+1)
char_dict[str1] = j
len = max(len, j-i+1)
return len

a = Solution()

print(a.lengthOfLongestSubstring(''))
print(a.lengthOfLongestSubstring('c'))
print(a.lengthOfLongestSubstring('au'))
print(a.lengthOfLongestSubstring('abcabcbb'))
print(a.lengthOfLongestSubstring('bbbbb'))
print(a.lengthOfLongestSubstring('pwwkew'))
print(a.lengthOfLongestSubstring('pvpe'))
# print(a.lengthOfLongestSubstring('abba'))

TAG:

 

评分:0

我来说两句

Open Toolbar