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

2024-10-02 20:38:47

本文实例讲述了Python实现查找字符串数组最长公共前缀。分享给大家供大家参考，具体如下：

编写一个函数来查找字符串数组中的最长公共前缀。

class Solution:
  def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    olds = ''
    rs=''
    if not strs:
      return ''
    if len(strs)==1:
      return strs[0]
    over = False
    print("strs_len:", len(strs))
    i=0 # 单个字符的索引
    while True:
      j=0 # strs中字符串的索引
      while j < len(strs)-1:
        if not strs[j] or not strs[j+1]:# 若是空串
          break
        #print("s1:",len(strs[j]), " s2:", len(strs[j+1]))
        if i >= len(strs[j]): # 如果一个子串比较完了，则结束循环
          over = True
          break
        elif i >= len(strs[j+1]):
          j+=1
          over = True
          break
        else:
          over = False
        #print("j:",j,"i: ",i)
        if strs[j][i] != strs[j+1][i]:
          break
        j+=1
      #print("j2:",j)
      if not over and j!=(len(strs)-1): # 如果没有比较到最后，说明前面出现了不相等的子串
        break
      #print("j:",j,"i: ",i)
      if over: # 如果一个子串已经比较结束，结束循环
        rs=strs[j]
        break
      i+=1
      rs=strs[0][:i]
      print("rs:",rs)
    return rs

我实现的方法，相当笨，后来通过测试后，我发现原来系统中有现成的接口是现实这个功能，如下：

os.path.commonprefix(list)

返回list中，所有元素共有的最长的前缀

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

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

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

● 脚本用途遍历文件夹下的文件,消除文件名前的特征字符串. ● 脚本实现 import os,sys import re from string import Template div = r"." ############################################################################### # @Function: description #######################################
python使用正则表达式来获取文件名的前缀方法

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

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

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

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

字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m
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字符串匹配算法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查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):
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实现求两个字符串的最长公共子串方法

如下所示: # 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二分查找+字符串模板+textwrap模块,

目录二分查找字符串模板 textwrap 模块按照空格统计词组个数用 “0” 填充字符串前言: 这个系列的专栏是为了保持 Python 手感而创建的,也可以用来学习 Python,因为存在知识跨越难度,所以先学习滚雪球系列为佳. 二分查找问题场景在一个升序的数组中(其实就是一个只有整数的列表),查找一个目标数的下标,不存在返回 -1 . 解决思路因为数组是升序的,所以二分查找就能落地了先取出数组中的中间值,与目标数比较大小,确定一半的范围然后重复上述步骤不断缩小范围即可. 编
在JavaScript中查找字符串中最长单词的三种方法(推荐)

本文基于Free Code Camp基本算法脚本"查找字符串中最长的单词". 在此算法中,我们要查看每个单词并计算每个单词中有多少个字母.然后,比较计数以确定哪个单词的字符最多,并返回最长单词的长度. 在本文中,我将解释三种方法.首先使用FOR循环,其次使用sort()方法,第三次使用reduce()方法. 算法挑战返回提供的句子中最长单词的长度. 您的回复应该是一个数字. 提供的测试用例 findLongestWord("The quick brown fox jumpe
C语言求两个字符串的最长公共子串

本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st
Java最长公共子序列示例源码

最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列.其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续.关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容. 之前看过一个LCS算法的实现过程,觉得太过繁琐.自己写了一个比较简单的,此处仅仅介绍实现过程. 程序代码测试通过,需要的童鞋
Python求两个字符串最长公共子序列代码实例

一.问题描述给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X
JavaScript自定义函数实现查找两个字符串最长公共子串的方法

本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= "" ,L1=s1.length,L2=s2.length; if (L1>L2){ var s3=s1;s1=s2,s2=s3,L1=s2.length;} for ( var j=L1;j> 0 ;j--) for ( var i= 0 ;i&

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

相关推荐

随机推荐