栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

【一个常规的算法,最长公共前缀,Python】

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【一个常规的算法,最长公共前缀,Python】

@[TOC

给定一串字符串,要求提取其中重复率最高的字符串(不包含单字符串),

思路分析

采取分段进行遍历的方式,达到出现所有情况为止
"给定「abcabc」
固出现情况为:

[('ab', 2), ('bc', 2), ('abc', 2), ('ca', 1), ('bca', 1), ('cab', 1), ('abca', 1), ('bcab', 1), ('cabc', 1), ('abcab', 1), ('bcabc', 1), ('abcabc', 1)]
具体逻辑
'''先根据题意具体分析
要求输入不定长字符串,查找重复,不包含单字符串的情况下
起始长度为 2'''

'''将字符串具体进行切片思路
传入字符串进行按指定长度切片,但为保证最后一次切片不为空或不为单字符,固在指定
长度字符串的基础上进行减字符串的长度且因range方法问题,所以在长度上进行+1操作
最后将切片完成的字符串进行保存,代码如下'''
def Slice(ins_str,length):
    result_list = []
    for i in range(len(ins_str) - length + 1):
        result_list.append(ins_str[i:i + length])
    return result_list
'''如此是单间距的方法,延伸一下,进行遍历循环操作'''
glo_list = []
for i in range(2, len(ins_str) +1):
    ret_list = Slice(ins_str, i)
    glo_list += ret_list
'''循环操作完毕后,glo_list中保存的就是所有可以出现的情况
接下来进行统计方法,采用将出现的情况作为KEY 重复次数作为VALUE,以此进行统计,然后根据键值排序确定重复最高的字符串'''
for i in range(len(glo_list)):
    if glo_list[i] in glo_dict:
        glo_dict[glo_list[i]] += 1
    else:
        glo_dict[glo_list[i]] = 1

'''进行排序操作,转为可遍历的元祖数组后进行按重复数进行排序操作'''
result_dict = sorted(glo_dict.items(), key=lambda e: e[1], reverse=True)  # 倒序排序

'''
如上,输入 ”hello world“
结果,输出”[('he', 1), ('el', 1), ('ll', 1), ('lo', 1), ('o ', 1), (' w', 1), ('wo', 1), ('or', 1), ('rl', 1), ('ld', 1), ('hel', 1), ('ell', 1), ('llo', 1), ('lo ', 1), ('o w', 1), (' wo', 1), ('wor', 1), ('orl', 1), ('rld', 1), ('hell', 1), ('ello', 1), ('llo ', 1), ('lo w', 1), ('o wo', 1), (' wor', 1), ('worl', 1), ('orld', 1), ('hello', 1), ('ello ', 1), ('llo w', 1), ('lo wo', 1), ('o wor', 1), (' worl', 1), ('world', 1), ('hello ', 1), ('ello w', 1), ('llo wo', 1), ('lo wor', 1), ('o worl', 1), (' world', 1), ('hello w', 1), ('ello wo', 1), ('llo wor', 1), ('lo worl', 1), ('o world', 1), ('hello wo', 1), ('ello wor', 1), ('llo worl', 1), ('lo world', 1), ('hello wor', 1), ('ello worl', 1), ('llo world', 1), ('hello worl', 1), ('ello world', 1), ('hello world', 1)]“
'''



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/1002462.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号