目录

三、字符串简介

3.1 最长公共前缀

3.2 最长回文子串

3.3 翻转字符串里的单词

3.4 实现 strStr (选修字符串匹配算法&＃xff1a;KMP) (未完)

三、字符串简介

3.1 最长公共前缀

3.1.1 问题描述

3.1.2 求解过程

法一&＃xff1a;注意是“公共”前缀&＃xff0c;而 不是“出现次数最多的”前缀&＃xff0c;因此&＃xff0c;每次只需要判断前缀切片出现次数是否等于列表中字符串总数即可。一旦前缀切片出现频次小于字符串总数&＃xff0c;则不满足公共&＃xff0c;停止寻找。(审题很重要&＃xff01;)

2020/06/04 - 24.13% - 使用了太多技巧&＃xff0c;复杂度太高&＃xff01;效率很低&＃xff01;且冗余计算很多&＃xff01;

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:num &＃61; len(strs) # 字符串总数if num &＃61;&＃61; 0: # 特殊情况 []return ""if num &＃61;&＃61; 1: # 特殊情况 [""] ["ab"]return strs[0]f &＃61; "" # 初始化输出前缀字符串max_len &＃61; len(max(strs, key&＃61;lambda x: len(x))) # 最长字符串长度for i in range(1, max_len&＃43;1): # 使用切片不会有 index out of range 的问题f_temp, n_temp &＃61; collections.Counter(map(lambda y: y[:i], strs)).most_common()[0] if n_temp &＃61;&＃61; num: # 如果该前缀出现频次&＃61;字符串总数f &＃61; f_temp # 将其作为输出前缀字符串else:return freturn f

法二&＃xff1a;注意到&＃xff0c;作为“公共”前缀&＃xff0c;事实上根本不需要那么多技巧和遍历。只需要选其中一个单词切片&＃xff0c;遍历数组依次对比以确定当前切片是否是“公共”的。一旦发现非公共&＃xff0c;直接返回当前切片。否则&＃xff0c;扩大切片范围再遍历一次。

2020/06/04 - 77.66% - 思路有对&＃xff0c;可以继续优化&＃xff01;

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if len(strs) &＃61;&＃61; 0:return ""result &＃61; "" # 初始化输出结果first_str &＃61; strs[0] # 首单词for i in range(1, len(first_str)&＃43;1): # 根据参考答案, 使用 find 可以简化 for 后操作cur_front &＃61; first_str[:i] # 当前前缀#for j in range(1, length): # 用单纯的 for 比 enumerate 慢 20%# if strs[j][:i] !&＃61; cur_front:for _, cur_str in enumerate(strs):if cur_str[:i] !&＃61; front: # 但凡发现一个不一样, 直接 returnreturn resultresult &＃61; cur_front # 遍历数组, 确定公共前缀return result

法三&＃xff1a;参考写法&＃xff0c;太强了&＃xff0c;充分利用 Python 特性&＃xff1a;zip() 拉链函数 &＃43; * 打包 &＃43; 集合 set 等实现最优化&＃xff0c;化繁为简&＃xff0c;佩服&＃xff01;经过观察&＃xff0c;最快的方法 无一不是使用 zip() 函数。

2020/06/04 - 99.99% - 最快&＃xff01;

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:res &＃61; ""# 通过 zip 缝合所有元素, 超过最短的部分会被截断for i in zip(*strs): #print(i)if len(set(i)) &＃61;&＃61; 1: # 使用集合判断当前位置字符是否公共res &＃43;&＃61; i[0]else:break return res

3.2 最长回文子串

3.2.1 问题描述

3.2.2 求解过程

法一&＃xff1a;朴素法&＃xff0c;从宽到窄的滑动窗口&＃xff0c;依次对其中的字符串切片进行正、逆序比较。一旦符合比较&＃xff0c;就是当前最长的回文字符串了&＃xff0c;直接返回之。否则&＃xff0c;找到最后也没有&＃xff0c;就随意返回一个字符。复杂度 O(n^3)。

2020/06/04 - 36.83% - 看来不怎么样&＃xff01;(4752 ms太低效了)

class Solution:def longestPalindrome(self, s: str) -> str:length &＃61; len(s)if length <&＃61; 1: # 特殊情况如 "" "a"return stimes &＃61; 1 # 首次用全长窗口, 只需要比较1次for width in range(length, 0, -1): # 滑动窗口宽度-1for start in range(times): # 滑动窗口移动次数 timeswindow &＃61; s[start:start&＃43;width] # 滑动窗口内字符串切片if window &＃61;&＃61; window[::-1]: # 正序逆序比较return windowtimes &＃43;&＃61; 1 # 滑动窗口宽度-1时,移动次数&＃43;1return s[0] # 如果一直找不到就随意返回一个字符

法二&＃xff1a;参考答案&＃xff0c;原理待回顾。

2020/06/04 - 99.94% - 最快&＃xff01;(52 ms)

class Solution:def longestPalindrome(self, s: str) -> str:length &＃61; len(s)if length <2 or s &＃61;&＃61; s[::-1]:return selse:max_length &＃61; 1 start_pointer &＃61; 0 for i in range(1, length):even &＃61; s[i-max_length: i&＃43;1] # 切片odd &＃61; s[i-max_length-1: i&＃43;1] # 切片if (i - max_length-1 >&＃61; 0) and (odd &＃61;&＃61; odd[::-1]):start_pointer &＃61; i - max_length - 1 max_length &＃43;&＃61; 2continueif (i - max_length >&＃61; 0) and (even &＃61;&＃61; even[::-1]):start_pointer &＃61; i - max_lengthmax_length &＃43;&＃61; 1return s[start_pointer: start_pointer&＃43;max_length]

3.3 翻转字符串里的单词

3.3.1 问题描述

3.3.2 求解过程

法一&＃xff1a;朴素法&＃xff0c;使用 split(" ") 将原字符串以 " " 为间隔划分为字符串列表&＃xff0c;使用 [::-1] 反转字符串列表。注意&＃xff0c;此时字符串列表仍包含有空字符串。为此&＃xff0c;通过 for 循环筛选出非空字符串并加入结果字符串 res 中&＃xff0c;然后加入字符串间隔空格。最后&＃xff0c;使用 str.rstrip() 删除末端空格。复杂度 O(n)。

2020/06/06 - 90.57% - 朴素的思路

class Solution:def reverseWords(self, s: str) -> str:res &＃61; ""tmp &＃61; s.split(" ")[::-1]for word in tmp:if word:res &＃43;&＃61; wordres &＃43;&＃61; " "return res.rstrip()

法二&＃xff1a;组合 Python 字符串方法 split() 和 join() 实现拆分和重组&＃xff0c;通过 list[::-1] 反转中间形式的字符串列表。复杂度 O(n)。

2020/06/06 - 99.99% - 虽然最快&＃xff0c;但是太依赖内建方法。

class Solution:def reverseWords(self, s: str) -> str:if not s:return ""word_list &＃61; s.split()[::-1] # 获取所有有效的字符串列表并反转strs &＃61; " ".join(word_list) # 将列表元素以" "为间隔合成新字符串return strs# return " ".join(s.split()[::-1]) # 以上可一言以蔽之

3.4 实现 strStr (选修字符串匹配算法&＃xff1a;KMP)

3.4.1 问题描述

3.4.2 求解过程

法一&＃xff1a;(基准) 直接使用 Python 字符串内置方法 str.find() 实现查找匹配。如果这样写&＃xff0c;面试官肯定要把你踢出去的......

2020/06/07 - 60.60% - 看来还不是最快的&＃xff01;

class Solution:def strStr(self, haystack: str, needle: str) -> int:return haystack.find(needle)

 法二&＃xff1a;(暴力匹配改) 不同于每次都在 haystack 上滑动窗口取出切片来与 needle 比较的暴力匹配方式&＃xff0c;本方法先试探性比较首字母&＃xff0c;倘若相同才有兴趣比较全部&＃xff0c;从而节省了大量时间。复杂度 O(n) 吗&＃xff1f;(怎么算啊&＃xff1f;)

202/06/08 - 97.06% - 看来还行

class Solution:def strStr(self, haystack: str, needle: str) -> int:if not needle: # len(needle) &＃61;&＃61; 0 返回 0return 0lenh &＃61; len(haystack)lenn &＃61; len(needle)if lenh

法三&＃xff1a;(KMP 算法)&＃xff1a;待续。。。