leetcode 14. 最长公共前缀 (绝对想不到的解法)

题目在这:https://leetcode-cn.com/problems/longest-common-prefix/

先说一下传统的解法，毕竟刷leecode是为了提升算法能力，直接用函数不太可取哈哈.
题目要找最长公共前缀，是前缀~~~差点看错找公共子序列了 我dp都建好了(狗头)

要点:
任何字符串和空字符都是没有公共字符的,也就是说我们只需要找最短的字符串拿出来比较就行了。
比如 str = [‘abc’,‘ab’,‘a’] 显然我们只需要拿最短的字符串 ‘a’ 和其他的两个字符串第一位比看是不是a就可以了。

上代码!

strs = ["dog","racecar","car"]
lenght = len(strs[0])
for i in range(len(strs)):  # 先找出来最短的那个字符串
    if  len(strs[i]) < lenght:
        lenght = len(strs[i])
temp = True
res = 0  
for i in range(lenght): 
    for j in range(len(strs)-1):
        if strs[j][i] != strs[j+1][i]:
            temp = False
    if temp:
        res += 1 # 统计有多少位是一样的
st = ''
if res:
    for i in range(res):  # 循环遍历res 吧相同的字母放到st里
        st += strs[0][i]  # 这样st里就是存的公共前缀了
    print(st)
else:
    print(' ')

里面的两层循环要想好，比较容易错，反正我就在这错了哈哈。
外层循环是控制字符串当前比较的第几位，而里面的for用来转移到一下字符串。拿代码模拟一遍就理解了…

绝妙解法:

要点:

1.python里的zip()函数 :用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组。
2.set()变成集合，可以做到除重的效果.
3.*str 解压参数 拆包…
比如:

strs = ["flower","flow","flight"]
当我们使用 *strs之后 变成....
flower flow flight
------------------------------------
for i in zip(*strs)
则 i 输出为:
('f', 'f', 'f')
('l', 'l', 'l')
('o', 'o', 'i')
('w', 'w', 'g')

zip将每个字符串的每一位一一对应起来.
空字符不算，应该是zip的特性，可以参考https://www.runoob.com/python/python-func-zip.html
这时候使用set()的特性—去重。
去重之后如果只有一个字母--------所有字符串中相同位都是同样的字母
去重之后如果包含一个以上的字母-------字母有所不同

完整代码:

strs = ["flower","flow","flight"]
res = ""
for tmp in zip(*strs):
    print(tmp)
    tmp_set = set(tmp)
    if len(tmp_set) == 1:
        res += tmp[0]
    else:
        break
print(res)

这段代码是在leetcod评论区看到的，看完之后惊到了。
也是自己对python语法理解不够深刻，属实想不到。

不过大家还是要着重理解普通的算法解法，毕竟还要面试啥的…

--------------一个小白的刷题笔记