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

yipeiwu_com6年前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函数定义及传参方式详解(4种)

一、函数初识 1、定义:将一组语句的集合通过一个名字(函数名)封装起来,要想执行这个函数,只需调用其函数名即可。  2、好处:代码重用;保持一致性;可扩展性。 3、示例如下:    ...

python实现电子书翻页小程序

python实现电子书翻页小程序

本文实例为大家分享了python实现电子书翻页的具体代码,供大家参考,具体内容如下 1.题目: 电子书翻页: (1)自动翻页:每次默认读三行,读完之后睡两秒,直到把所有内容全部读出来 (...

对Django的restful用法详解(自带的增删改查)

对Django的restful用法详解(自带的增删改查)

什么是rest REST是所有Web应用都应该遵守的架构设计指导原则。 Representational State Transfer,翻译是”表现层状态转化”。 面向资源是REST最明...

深入学习python多线程与GIL

python 多线程效率 在一台8核的CentOS上,用python 2.7.6程序执行一段CPU密集型的程序。 import time def fun(n):#CPU密集型的程序...

讲解Python中的标识运算符

讲解Python中的标识运算符

 下表列出了所有Python语言支持的标识运算符。 示例: 试试下面的例子就明白了所有Python编程语言提供的标识运算符: #!/usr/bin/python a =...