一个求解数组字符串最长公共前缀的问题

最近面试被问到一个求解字符串公共前缀的问题,当时没注意,脚本写了一半，最后又画了一下条件和问题，用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"] 输出""

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