字符串问题---找到字符串的最长无重复字符子串

发布于:2021-09-13 10:18:28

【题目】


  给定一个字符串str,返回str中最长无重复字符子串的长度。


【举例】


  str = “abcd”,返回4。
  str = “aabcb”,返回3。


【基本思路】


  如果str的长度为N,字符的编码范围为M,本题可以做到时间复杂度为O(N),空间复杂度O(M)。具体方法如下:


    在遍历str之前,先申请几个变量。哈希表map,key表示某个字符,value为这个字符最*出现的位置。整型变量pre,如果当前遍历到的字符为str[i],pre表示必须以str[i-1]结尾的情况下,最长无重复字符子串开始位置的前一个位置,初始时pre = -1。全局变量length保存出现的最长长度。从左到右依次遍历str,遍历到str[i]时,计算必须以str[i]结尾的最长无重复字符子串的长度。

    map[str[i]]表示之前出现str[i]字符的位置,假设该位置是a。以str[i]结尾的无重复子串必然不包括a位置。

    根据pre的定义可知,在以str[i-1]为结尾的情况下,最长无重复子串的长度为(i-1)- pre,此时如果a的位置在pre的右边,则以str[i]结尾的最长子串的长度为 i - a;如果a的位置在pre的左边,则以str[i]结尾的最长子串的长度为i - pre。这个问题画个图就很直观了,这里不多解释。

    计算完长度以后,pre位置和a位置哪一个在右边就作为新的pre的值。然后去计算下一个位置的字符,整个过程用length保存出现的最大值。


下面是使用python3.5实现的代码。


#找到字符串的最长无重复字符子串
#使用哈希表
def maxUniqueStr(str1):
if str1 == None or len(str1) == 0:
return ""
map = {}
pre = -1
length = 0
for i in range(len(str1)):
if str1[i] in map:
pre = max(pre, map[str1[i]])
length = max(length, i-pre)
map[str1[i]] = i
return length


#使用数组
def maxUniqueStr2(str1):
if str1 == None or len(str1) == 0:
return ""
map = [-1 for i in range(256)]
pre = -1
length = 0
for i in range(len(str1)):
pre = max(pre, map[ord(str1[i])])
length = max(length, i-pre)
map[ord(str1[i])] = i
return length

相关推荐

最新更新

猜你喜欢