Chinaunix首页 | 论坛 | 博客
  • 博客访问: 697086
  • 博文数量: 98
  • 博客积分: 3145
  • 博客等级: 中校
  • 技术积分: 1902
  • 用 户 组: 普通用户
  • 注册时间: 2008-12-15 12:52
文章分类
文章存档

2021年(1)

2020年(1)

2016年(8)

2015年(3)

2014年(1)

2013年(5)

2012年(4)

2011年(9)

2010年(12)

2009年(42)

2008年(12)

我的朋友

分类: Python/Ruby

2021-04-22 17:54:03

最近面试被问到一个求解字符串公共前缀的问题,当时没注意,脚本写了一半,最后又画了一下条件和问题,用python完善了一下脚本,内容如下:

注意: 解题的方法应该有好多,我这里就是根据自己写了一半的脚本完善了一下。

问题:求下面已知数组中字符串的最长公共前缀

例如:

["flower","flow","flight"] 字符串最长公共前缀为fl,执行完程序输出fl

如果输入的数组字符串没有公共前缀,输出"",例如:["dog","racecar","car"]

思路:

第一次写忘记了最长前缀这个要求,写的时候输出的结果是"fl",但解出的是最大公共字符。

#!/usr/bin/env python
s=["flowera","flowa","flighta"]
k={}
out=''
for i in s:    
    for  zl in i[0:]:        
        if zl in k.keys(): 
            k[zl]+=1        
        else:            
            k[zl]=0
for i in k:    
    if k[i]>=len(s)-1:        
        out+=i
print(out)

最后面试官提醒,才发现少了"最长前缀"的要求,但由于时间问题,就没有在这个代码上过多的纠结,但面试完后,我重新分析了下问题,发现这个解题思路也是可以完成需求的,最终完善了这个思路,将脚本写完,如下:

#!/usr/bin/env python
s=["flowera","flowa","flighta"]
k={}
out=''
eout=''
for i in s:    
    for  zl in i[0:]:        
        if zl in k.keys(): 
            k[zl]+=1        
        else:            
            k[zl]=0
for i in k:    
    if k[i]>=len(s)-1:        
        out+=i
#print(out)
for  i ins[0]:    
    if i in out:        
        eout+=i    
    else:        
        break
print(eout)

全部的解题思路是这样的:

  1. 先求出所有数组字符串的最大公共字符(即每个字符串都出现过的字符),放到一个字符串中
  2. 任意从给出的数组中取1个字符串,从前缀首字母开始遍历只要在存在与最大公共字符串中出现,就认为是前缀字符,按顺序存储到最大前缀字符串中,顺序取前缀字符进行比较,只要有一个字符不在最大公共字符串中,就停止循环,输出最大前缀字符串,如果没有获取到,最终输出的最大公共前缀的字符串就是空的

按照要求,输入字符串为

["flower","flow","flight"] 输出"fl"

["flowear","flowa","flighta"] 输出"fl"

["dog","racecar","car"] 输出""

符合要求,本解题方法仅供参考,网络上还有其他的解决方案,也可以去查看一下

阅读(1273) | 评论(0) | 转发(0) |
0

上一篇:Centos通过yum方式安装python3.6

下一篇:没有了

给主人留下些什么吧!~~