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

本文主要是介绍一个求解数组字符串最长公共前缀的问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

这篇关于一个求解数组字符串最长公共前缀的问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！