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

yipeiwu_com7年前Python基础

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

题目描述

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

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

算法示例:

# -*- coding:utf-8 -*-
#! python3
class 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]] += 1
inputString = 'arabcacfr'
sol = Solution()
sol.longestSubString(inputString)
print(sol.maxString)
#输出:['rabc', 'acfr']

运行结果:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

相关文章

python读取指定字节长度的文本方法

软件版本 Python 2.7.13; Win 10 场景描述 1、使用python读取指定长度的文本; 2、使用python读取某一范围内的文本。 Python代码 test.txt文...

python 定时器,轮询定时器的实例

python 定时器默认定时器只执行一次,第一个参数单位S,几秒后执行 import threading def fun_timer(): print('Hello Timer...

Python中的延迟绑定原理详解

直接看下面例子 my_ld = [lambda x:x*i for i in range(3)] my_list = [ld(2) for ld in my_ld] print(my...

浅谈python编译pyc工程--导包问题解决

浅谈python编译pyc工程--导包问题解决

利用python 编译工程,生产pyc文件 pyc文件好处:是一种二进制机器码,并且隐藏了源文件代码,但是有和py文件一样的功能(可以理解为效果一样) 所以可以将代码隐藏,便于商业价值,...

使用python编写脚本获取手机当前应用apk的信息

前提是已设置ANDROID_HOME环境变量,使用aapt工具获取apk的信息,保存至脚本所在目录下的PackageInfo.txt文件中: import os import te...