最近面试被问到一个求解字符串公共前缀的问题,当时没注意,脚本写了一半,最后又画了一下条件和问题,用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个字符串,从前缀首字母开始遍历只要在存在与最大公共字符串中出现,就认为是前缀字符,按顺序存储到最大前缀字符串中,顺序取前缀字符进行比较,只要有一个字符不在最大公共字符串中,就停止循环,输出最大前缀字符串,如果没有获取到,最终输出的最大公共前缀的字符串就是空的
按照要求,输入字符串为
["flower","flow","flight"] 输出"fl"
["flowear","flowa","flighta"] 输出"fl"
["dog","racecar","car"] 输出""
符合要求,本解题方法仅供参考,网络上还有其他的解决方案,也可以去查看一下