Python查找最长不包含重复字符的子字符串算法示例

2019-11-25 13:18:05

字体：大中小

来源：转载

供稿：网友

本文实例讲述了Python查找最长不包含重复字符的子字符串算法。分享给大家供大家参考，具体如下：

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。例如在“arabcacfr”中，最长的不包含重复字符的子字符串是“acfr”，长度为4

采用字典的方法，最后输出所有最长字符的列表

算法示例：

# -*- coding:utf-8 -*-#! python3class Solution:  def __init__(self):    self.maxString = []  def longestSubString(self, inputString):    if inputString == '':      return ''    dic = {}    dic = dic.fromkeys(inputString, 0)    self.maxString.append(inputString[0])    for i in range(len(inputString)):      for j in range(i, len(inputString)):        if dic[inputString[j]] != 0:          dic = dic.fromkeys(inputString, 0)          break        else:          if j - i + 1 > len(self.maxString[0]):            self.maxString = []            self.maxString.append(inputString[i:j+1])          elif j - i + 1 == len(self.maxString[0]):            self.maxString.append(inputString[i:j+1])          dic[inputString[j]] += 1inputString = 'arabcacfr'sol = Solution()sol.longestSubString(inputString)print(sol.maxString)#输出：['rabc', 'acfr']

运行结果：