首页 > 代码库 > 面试宝典_Python.常规算法.0002.输出任意两个字符串中最长公共子串?
面试宝典_Python.常规算法.0002.输出任意两个字符串中最长公共子串?
面试题目:
1. 用PY实现求任意两个字符串最长的公共子串?
解题思路:
1. 先求出长度最小的字符串,然后遍历其索引,这样可以避免字符串索引溢出,然后判断对应索引的值是否相同,相同的话就加到目标字典,不同的话就更新目标字典索引,但不存储,最后再按照值长度逆向排序取出第一个元素即可.
具体实现:
#!/usr/bin/env python # -*- coding: utf-8 -*- """ # # Authors: limanman # OsChina: http://xmdevops.blog.51cto.com/ # Purpose: # """ # 说明: 导入公共模块 # 说明: 导入其它模块 def get_most_part(sstr, tstr): s_len = len(sstr) t_len = len(tstr) r = {} count = 0 # 说明: 遍历长度较小者长度防止溢出 for i in xrange(s_len if s_len <= t_len else t_len): # 说明: 如果两个字符相同则追加 if sstr[i] == tstr[i]: r.setdefault(count, []).append(sstr[i]) else: # 说明: 否则改变字典索引 count = i # 说明: 对结果集排序 value = sorted(r.itervalues(), key=lambda _: len(_), reverse=True) if not value: return ‘‘ return ‘‘.join(value[0]) if __name__ == ‘__main__‘: print get_most_part(‘ayx‘, ‘yxz‘)
本文出自 “满满李 - 运维开发之路” 博客,请务必保留此出处http://xmdevops.blog.51cto.com/11144840/1888889
面试宝典_Python.常规算法.0002.输出任意两个字符串中最长公共子串?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。