Python版本自己都写的这么长，虽然对于例子都通过了，但是在leetcode运行的时候还是通不过，主要是因为起初想算法的时候，疏漏了很关键的东西，其起初的思路是：在遍历字符串的时候，遇到重复的字符就截取一个字串，然后计算所得到的子串中长度最大的返回，如果字符串为空的话返回0，如果没有重复的字符返回字符串的长度
自己失败的版本：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
temp = []
dict = {}
point = 0
count1 = 0
if len(s) == 0:
return 0
for char in s:
point = point + 1
if char in temp:
dict[point] = temp
temp = []
temp.append(char)
else:
temp.append(char)
count1 = count1 + 1
if len(s) == count1:
return len(s)
dict[point + 1] = temp
a = []
for key in dict:
print dict[key]
a.append(len(dict[key]))
return max(a)
讨论板上比较不错的Java和Python
Java
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
利用hashmap找到前一个相同字符的位置,那么着这两者之间的距离就是以当前字符结尾的最长substring.比较目前max的大小,看是否需要更新.还要记得更新一下字符的位置,因为会有重复
Python
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength
转载请注明原文地址: https://ju.6miu.com/read-13613.html
