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实现字符串匹配算法代码示例
字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符 蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m
-
Python实现的破解字符串找茬游戏算法示例
本文实例讲述了Python实现的破解字符串找茬游戏算法.分享给大家供大家参考,具体如下: 最近在一个QQ群里发现有那种机器人, 发出来字符串找茬游戏: 有点类似于: 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没役没没没没没没没没没没没没 没没没没没没没没役没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 玩法就是用户发消息到群里: #找茬 然后群里有个自动聊天的机器人, 他接到这句话之后, 会将上面一大堆文字
-
python 实现求解字符串集的最长公共前缀方法
问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li
-
python之消除前缀重命名的方法
● 脚本用途 遍历文件夹下的文件,消除文件名前的特征字符串. ● 脚本实现 import os,sys import re from string import Template div = r"." ############################################################################### # @Function: description #######################################
-
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实现查找字符串数组最长公共前缀示例
本文实例讲述了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 自带的翻转 函数 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使用正则表达式来获取文件名的前缀方法
在我们处理文件的时候,会遇到这样的一种场景,我们需要对某个文件进行操作,然后生成与原文件名相同的文件(只是文件格式改变).那么这个时候就可以使用正则表达式来匹配我们所需要的字符串. 实现 import re test='kasduabshdvkjASVKDV.txt' m=re.findall(r'(.+?)\.',test) print(m) 我们所使用的是python正则表达式库,re库来进行快速正则匹配.对此不熟悉的朋友可以去看看相关的知识.在这里我简单的说下 r'(.+?)\.'这里面的
-
Python查找最长不包含重复字符的子字符串算法示例
本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表 算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):
-
Linux查找文件夹下包含某字符的所有文件
Linux grep 命令用于查找文件里符合条件的字符串.grep 指令用于查找内容包含指定的范本样式的文件,如果发现某文件的内容符合所指定的范本样式,预设 grep 指令会把含有范本样式的那一列显示出来.若不指定任何文件名称,或是所给予的文件名为 -,则 grep 指令会从标准输入设备读取数据. 标准格式: grep -r string ./ 示例: grep -r message ./ 示例解释:在当前目录下递归查找含有字符串message的文件 更多介绍: -r 是递归查找 -n 是显示行
-
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__:沂水寒
随机推荐
- 超简单超强悍的清理C盘垃圾文件方法
- JSP实现计算器功能(网页版)
- Web开发使用Angular实现用户密码强度判别的方法
- httpclient模拟post请求json封装表单数据的实现方法
- 请求如何进入ASP.NET MVC框架
- php优化及高效提速问题的实现方法第1/2页
- C#判断指定文件是否是只读的方法
- c++实现跳跃表(Skip List)的方法示例
- IOS关闭键盘的方法
- node.js 中国天气预报 简单实现
- Discuz 模板语句分析及知识技巧
- Linux复制文件命令cp之使用解说
- 可以查杀sxs.exe的bat(批处理)文件
- Log4j按级别输出日志到不同文件的实现方法
- 深入解析JavaScript中的数字对象与字符串对象
- IE中checkbox在刷新后初始化的问题
- 三层交换机发动防守反击
- Java是自学好还是参加培训班好?
- jquery实现的简单轮播图功能【适合新手】
- webpack的pitching loader详解