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

相关文章

Win10下python 2.7.13 安装配置方法图文教程

Win10下python 2.7.13 安装配置方法图文教程

本文记录了Windows10安装Python2.7的详细步骤,分享给大家。 一、下载软件 Python的官方地址 点击Downloads找到进行下载 点击进行下载、有18M左右 下...

python内存动态分配过程详解

python内存动态分配过程详解

一、前言 大多数编译型语言,变量在使用前必须先声明,其中C语言更加苛刻:变量声明必须位于代码块最开始,且在任何其他语句之前。其他语言,想C++和java,允许“随时随地”声明变量,比如...

Python pickle模块用法实例分析

本文实例讲述了Python pickle模块用法。分享给大家供大家参考。具体分析如下: pickle提供了一个简单的持久化功能。可以将对象以文件的形式存放在磁盘上。 pickle.dum...

Python 使用PIL numpy 实现拼接图片的示例

python纵向合并任意多个图片,files是要拼接的文件list # -*- coding:utf-8 -*- def mergeReport(files): from PIL...

详解Python3.6的py文件打包生成exe

详解Python3.6的py文件打包生成exe

原文提到的要点: 1. Python版本32位 (文件名为 python-3.6.1.exe) 2. 安装所有用到的模块(原文博主用的是openpyxl,我用到的有urllib中的req...