Python实现简单查找最长子串功能示例

本文实例讲述了Python实现简单查找最长子串功能。分享给大家供大家参考，具体如下：

题目选自edX公开课 MITx: 6.00.1x Introduction to Computer Science and Programming 课程 Week2 的Problem Set 1的第三题。下面是原题内容。

Assume s is a string of lower case characters.

Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, ifs = 'azcbobobegghakl', then your program should print

Longest substring in alphabetical order is: beggh
In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print

Longest substring in alphabetical order is: abc
For problems such as these, do not include raw_input statements or define the variable s in any way. Our automated testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.

代码如下：

# -*- coding:utf-8 -*-
#! python2
#判断一个字符串内的字母是否是按字母表顺序
# 如IsStrIncre('abbcdg') 返回 True
# IsStrIncre('abbadg') 返回 False
# 如果只有一个字符，也返回False
def IsStrIncre(s):
  for cnt in range(len(s) - 1):
    if len(s) == 1:
      return False
    elif s[cnt] > s[cnt+1]:
      return False
  return True
s = 'abajsiesnwdw'# example code
substr = ''
for length in range(1, len(s)+1):
  firstflag = True # a flag to remember the first string that satisfied the requirements
           # and ignore the strings satisfied the requirements but appeared after
  for cnt in range(len(s)-length+1):
    if IsStrIncre(s[cnt: cnt+length]):
      if firstflag:
        substr = s[cnt: cnt+length]
        firstflag = False
print 'Longest substring in alphabetical order is: ' + substr

运行结果：

Longest substring in alphabetical order is: ajs

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • python实现求最长回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

  • Python实现针对给定字符串寻找最长非重复子串的方法

    Python实现针对给定字符串寻找最长非重复子串的方法

    本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法.分享给大家供大家参考,具体如下: 问题: 给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如"aaaaaaaaaaaaa"那么满足要求的输出就是a 思路: 这里的思路有两种是我能想到的 (1)从头开始遍历字符串,设置标志位,在往后走的过程中当发现和之前标志位重合的时候就回头检查一下这个新出现的子串是否跟前面字符串或者前面字符串的子串相同,相同则记录该子串并计数加1,直至处理完毕 (2)利用滑窗切

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

  • Python最长公共子串算法实例

    本文实例讲述了Python最长公共子串算法.分享给大家供大家参考.具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x in s2 ] for y in s1 ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] =

  • Python简单实现查找一个字符串中最长不重复子串的方法

    本文实例讲述了Python简单实现查找一个字符串中最长不重复子串的方法.分享给大家供大家参考,具体如下: 刚结束的一个笔试题,很简单,不多说简单贴一下具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来一个字符串中最长不重复子串 ''' def find_longest_no_repeat_substr(one_str): ''''' 找出来一个字符串中最长不重复子串 ''' res_list=[] le

  • 详解Python最长公共子串和最长公共子序列的实现

    详解Python最长公共子串和最长公共子序列的实现

    最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度

  • python实现求两个字符串的最长公共子串方法

    如下所示: # coding:utf-8 ''' 求两个字符串的最长公共子串 思想:建立一个二维数组,保存连续位相同与否的状态 ''' def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位 maxNum = 0 # 最长匹配长度 p = 0 # 匹配的起始位 for

  • Python实现简单查找最长子串功能示例

    本文实例讲述了Python实现简单查找最长子串功能.分享给大家供大家参考,具体如下: 题目选自edX公开课 MITx: 6.00.1x Introduction to Computer Science and Programming 课程 Week2 的Problem Set 1的第三题.下面是原题内容. Assume s is a string of lower case characters. Write a program that prints the longest substring

  • Python实现简单的获取图片爬虫功能示例

    本文实例讲述了Python实现简单的获取图片爬虫功能.分享给大家供大家参考,具体如下: 简单Python爬虫,获得网页上的照片 #coding=utf-8 import urllib import re def getHtml(url): page = urllib.urlopen(url) html = page.read() return html def getImg(html): reg = r'src="(.+?\.jpg)" pic_ext' imgre = re.comp

  • Python 实现简单的shell sed替换功能(实例讲解)

    code: f = open('yesterday','r',encoding='utf-8') f2 = open('yesterday.bak','w',encoding='utf-8') old_str = input('请输入要修改的字符:') replace_str = input('请输入替换成的字符:') for line in f.readlines(): line = line.replace(old_str,replace_str) print(line) f2.write(

  • python开发任意表达式求值全功能示例

    目录 正文 完整的源代码 正文 在之前的基础上进一步实现了全功能表达式求值. 已支持浮点数 已支持字符串的处理,前加一个"(类似lisp语法) 支持减号/负号,一符两用机制 支持所有算术运算符,包括**,//, % 支持全部7个比较运算符 支持与或非3个逻辑运算符 支持自定义数学函数(代码中预设sin函数作为示范) 支持外部提供的变量机制 支持外部设置函数(代码中预设isvar函数作为示范) 支持列表 字典的支持,体现在外部的变量中 结构清晰,易于扩展 具有实用性及学习性 与其说距离DSL只有一

  • easyui-combobox 实现简单的自动补全功能示例

    前台:  Html页面 <input id="clsydw" name="clsydw" class="easyui-combobox" data-options="" /> JS //自动补全功能 $("#clsydw").combobox({ valueField:'syr', textField:'syr', panelWidth:200, panelHeight:'auto', onCh

  • vuejs2.0运用原生js实现简单的拖拽元素功能示例

    vuejs2.0运用原生js实现简单的拖拽元素功能示例

    整理文档,搜刮出一个vuejs2.0运用原生js实现简单的拖拽元素功能示例,留作笔记. <!DOCTYPE html> <html> <head> <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"/> <meta

  • Python使用matplotlib实现绘制自定义图形功能示例

    Python使用matplotlib实现绘制自定义图形功能示例

    本文实例讲述了Python使用matplotlib实现绘制自定义图形功能.分享给大家供大家参考,具体如下: 一 代码 from matplotlib.path importPath from matplotlib.patches importPathPatch import matplotlib.pyplot as plt fig, ax = plt.subplots() #定义绘图指令与控制点坐标 #其中MOVETO表示将绘制起点移动到指定坐标 #CURVE4表示使用4个控制点绘制3次贝塞尔曲

  • python 最简单的实现适配器设计模式的示例

    适配器设计模式是懒得改动某些代码,或者某些接口不方便改动的时候,使用一个特定的封装,一些特定的编写办法,使不同的接口可以使用同种调用方式使用. 更简单的说话则是,例如几个不同的接口 aliyun.qiniuyun.tencentyun是新增的接口,以前都是使用接口yun进行文件备份,现在每一种调用不同名都太烦,统一使用yun去进行aliyun.qiniuyun.tencentyun上传文件.这个时候就需要写一个适配器. 现在看一个简单例子,有一个类为Upload 是一个上传类,里面有一个方法是y

  • Python实现统计给定字符串中重复模式最高子串功能示例

    本文实例讲述了Python实现统计给定字符串中重复模式最高子串功能.分享给大家供大家参考,具体如下: 给定一个字符串,如何得到其中重复模式最高的子字符串,我采用的方法是使用滑窗机制,对给定的字符串切分,窗口的大小从1增加到字符串长度减1,将所有的得到的切片统计结果,在这里不考虑单个字符的重复模式,好了,很简单看具体实现: #!usr/binenv python #encoding:utf-8 ''''' __Author__:沂水寒城 统计一个给定字符串中重复模式数量得到最高重复模式串 '''

  • Python使用itchat模块实现简单的微信控制电脑功能示例

    本文实例讲述了Python使用itchat模块实现简单的微信控制电脑功能.分享给大家供大家参考,具体如下: #!/usr/bin/python #coding=UTF-8 import requests, json import itchat import os,time,datetime from PIL import ImageGrab from itchat.content import * app_dir = r''#打开一个程序,填写exe文件的绝对路径 imgdir = r'E:\t

随机推荐