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

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

相关文章

Django Admin中增加导出Excel功能过程解析

Django Admin中增加导出Excel功能过程解析

在使用Django Admin时, 对于列表我们有时需要提供数据导出功能, 如下图: 增加导出Excel功能 在Django Admin中每个模型的Admin类(继承至admin.M...

python 图像处理画一个正弦函数代码实例

python 图像处理画一个正弦函数代码实例

这篇文章主要介绍了python 图像处理画一个正弦函数代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 import num...

Pytorch 实现sobel算子的卷积操作详解

Pytorch 实现sobel算子的卷积操作详解

卷积在pytorch中有两种实现,一种是torch.nn.Conv2d(),一种是torch.nn.functional.conv2d(),这两种方式本质都是执行卷积操作,对输入的要求也...

python快速查找算法应用实例

本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考。 具体实现方法如下: import random def partition(list_object,start,...

PyTorch快速搭建神经网络及其保存提取方法详解

PyTorch快速搭建神经网络及其保存提取方法详解

有时候我们训练了一个模型, 希望保存它下次直接使用,不需要下次再花时间去训练 ,本节我们来讲解一下PyTorch快速搭建神经网络及其保存提取方法详解 一、PyTorch快速搭建神经网络...