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

赞 (0)

相关推荐

  • python 实现求解字符串集的最长公共前缀方法

    问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li

  • Python实现常见的回文字符串算法

    回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

  • Python实现的破解字符串找茬游戏算法示例

    本文实例讲述了Python实现的破解字符串找茬游戏算法.分享给大家供大家参考,具体如下: 最近在一个QQ群里发现有那种机器人, 发出来字符串找茬游戏: 有点类似于: 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没役没没没没没没没没没没没没 没没没没没没没没役没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 玩法就是用户发消息到群里: #找茬 然后群里有个自动聊天的机器人, 他接到这句话之后, 会将上面一大堆文字

  • Python实现字符串匹配算法代码示例

    字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符 蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m

  • python之消除前缀重命名的方法

    ● 脚本用途 遍历文件夹下的文件,消除文件名前的特征字符串. ● 脚本实现 import os,sys import re from string import Template div = r"." ############################################################################### # @Function: description #######################################

  • Python求一批字符串的最长公共前缀算法示例

    Python求一批字符串的最长公共前缀算法示例

    本文实例讲述了Python求一批字符串的最长公共前缀算法.分享给大家供大家参考,具体如下: 思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止. def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not st

  • Python字符串匹配算法KMP实例

    本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern

  • python使用正则表达式来获取文件名的前缀方法

    在我们处理文件的时候,会遇到这样的一种场景,我们需要对某个文件进行操作,然后生成与原文件名相同的文件(只是文件格式改变).那么这个时候就可以使用正则表达式来匹配我们所需要的字符串. 实现 import re test='kasduabshdvkjASVKDV.txt' m=re.findall(r'(.+?)\.',test) print(m) 我们所使用的是python正则表达式库,re库来进行快速正则匹配.对此不熟悉的朋友可以去看看相关的知识.在这里我简单的说下 r'(.+?)\.'这里面的

  • Python实现查找字符串数组最长公共前缀示例

    本文实例讲述了Python实现查找字符串数组最长公共前缀.分享给大家供大家参考,具体如下: 编写一个函数来查找字符串数组中的最长公共前缀. class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ olds = '' rs='' if not strs: return '' if len(strs)==1: retu

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

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

    本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表 算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):

  • Linux查找文件夹下包含某字符的所有文件

    Linux查找文件夹下包含某字符的所有文件

    Linux grep 命令用于查找文件里符合条件的字符串.grep 指令用于查找内容包含指定的范本样式的文件,如果发现某文件的内容符合所指定的范本样式,预设 grep 指令会把含有范本样式的那一列显示出来.若不指定任何文件名称,或是所给予的文件名为 -,则 grep 指令会从标准输入设备读取数据. 标准格式: grep -r string ./ 示例: grep -r message ./ 示例解释:在当前目录下递归查找含有字符串message的文件 更多介绍: -r 是递归查找 -n 是显示行

  • java实现统计字符串中字符及子字符串个数的方法示例

    java实现统计字符串中字符及子字符串个数的方法示例

    本文实例讲述了java实现统计字符串中字符及子字符串个数的方法.分享给大家供大家参考,具体如下: 这里用java实现统计字符串中的字符(包括数字.大写字母.小写字母以及其他字符)个数,以及字符串的子字符串的个数. 运行效果图如下: 具体代码如下: import java.util.Scanner; public class Counter { static Scanner scanner = new Scanner(System.in); public static void count(Str

  • Python实现删除排序数组中重复项的两种方法示例

    本文实例讲述了Python实现删除排序数组中重复项的两种方法.分享给大家供大家参考,具体如下: 对于给定的有序数组nums,移除数组中存在的重复数字,确保每个数字只出现一次并返回新数组的长度 注意:不能为新数组申请额外的空间,只允许申请O(1)的额外空间修改输入数组 Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1

  • Java使用正则表达式截取重复出现的XML字符串功能示例

    本文实例讲述了Java使用正则表达式截取重复出现的XML字符串功能.分享给大家供大家参考,具体如下: public static void main(String[] args) throws DocumentException { String s = "<MTCCommand Time=\"2014-03-22\"><Login UserId=\"admin\" UserPasswd=\"123\" />&l

  • Python实现的寻找前5个默尼森数算法示例

    本文实例讲述了Python实现的寻找前5个默尼森数算法.分享给大家供大家参考,具体如下: 找前5个默尼森数. 若P是素数且M也是素数,并且满足等式M=2**P-1,则称M为默尼森数.例如,P=5,M=2**P-1=31,5和31都是素数,因此31是默尼森数. python2代码如下: from math import sqrt def isPrime(n): 'judge whether a positive integer is a prime number!' if n==1: return

  • Python实现的插入排序，冒泡排序，快速排序，选择排序算法示例

    本文实例讲述了Python实现的插入排序,冒泡排序,快速排序,选择排序算法.分享给大家供大家参考,具体如下: #!/usr/bin/python # coding:utf-8 #直接插入排序 def insert_sort(list): for i in range(len(list)): Key = list [i] #待插入元素 j = i - 1 while(Key < list[j] and j >= 0): list[j+1] = list[j] #后移元素 list[j] = Ke

  • C++实现leetcode(3.最长无重复字符的子串)

    [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", wit

  • java 判断字符串中是否有重复字符的示例

    如下所示: /** * 判断字符串是否包含重复字符 * @param str * @return */ public static boolean containRepeatChar(String str){ if(str==null||str.isEmpty()){ return false; } char[] elements=str.toCharArray(); for(char e:elements){ if(str.indexOf(e)!=str.lastIndexOf(e)){ re

  • Python实现简单求解给定整数的质因数算法示例

    本文实例讲述了Python实现简单求解给定整数的质因数算法.分享给大家供大家参考,具体如下: 接着做题遇到求解质因数分解的问题,思想很简单,就是需要遍历从1到该整数本身,并且判断当数字为质数时加入列表最后输出即可,求解这样的一个正整数的质因数分解,关键在于理解,每次得到一个质因数之后需要更新整数为:原始整数除以这个质因数的值,循环直至原始整数的值小于2终止,输出结果即可,实现如下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒

随机推荐