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程序设计有所帮助。

相关文章

安装好Pycharm后如何配置Python解释器简易教程

安装好Pycharm后如何配置Python解释器简易教程

这两天有许多Python小白加入学习群,并且问了许多关于Pycharm基本使用的问题,今天小编就以配置Python解释器的问题给大家简单絮叨一下。 1、一般来说,当我们启动Pycharm...

使用Python编写vim插件的简单示例

 Vim 插件是一个 .vim 的脚本文件,定义了函数、映射、语法规则和命令,可用于操作窗口、缓冲以及行。一般一个插件包含了命令定义和事件钩子。当使用 Python 编写 vi...

python使用numpy读取、保存txt数据的实例

python使用numpy读取、保存txt数据的实例

1.首先生成array数组 import numpy as np a = np.random.rand(5,5) print(a) 结果: array([[0.17374613...

在Python中操作时间之mktime()方法的使用教程

 mktime()方法是localtime()反函数。它的参数是struct_time或全9元组,它返回一个浮点数,为了兼容时time()。 如果输入值不能表示为有效的时间,那...

Python 错误和异常代码详解

程序中的错误一般被称为 Bug,无可否认,这几乎总是程序员的错。。。 程序员的一生,始终伴随着一件事 - 调试(错误检测、异常处理)。反反复复,最可怕的是:不仅自己的要改,别人的也要改。...