Python 学习记录：力扣字符串专题第 3 题和第 5 题

Python 学习记录力扣字符串专题第 3 题和第 5 题前言今天我们从数组题刷到了字符串专题在老师的指导下完成了力扣第 3 题和第 5 题。第 3 题我用哈希集合和动态窗口两种解法完成第 5 题我分别用中心扩展和动态规划写出了两种解法。第一次发现同一道题可以有好几条路。一、第 3 题无重复字符的最长子串题目是找字符串里最长的、没有重复字符的连续子串。这道题我写了两种解法。方法一哈希集合思路枚举每个起点用set记录已经出现过的字符然后一直向右扩展遇到重复字符就停止每次更新最长长度。这个写法很直观但时间复杂度是 O(n²)。演示代码deflength_of_longest_substring(s):ans0foriinrange(len(s)):seenset()forjinrange(i,len(s)):ifs[j]inseen:breakseen.add(s[j])ansmax(ans,j-i1)returnans方法二动态窗口滑动窗口思路用左右两个指针维护一个窗口set记录窗口内的字符。右指针不断向右扩展如果遇到重复字符就让左指针一直右移直到重复字符被移出窗口每次更新最大长度。时间复杂度是 O(n)。演示代码deflength_of_longest_substring(s):seenset()left0ans0forrightinrange(len(s)):whiles[right]inseen:seen.remove(s[left])left1seen.add(s[right])ansmax(ans,right-left1)returnans运行结果abcabcbb返回3bbbbb返回1pwwkew返回3收获两种方法都用到了哈希集合set区别在于第一种只判断重复第二种还利用了窗口的连续性。老师让我对比两种解法的复杂度我才真正明白滑动窗口省在哪里。二、第 5 题最长回文子串回文就是正着读和倒着读都一样的字符串比如aba、bb。这道题我也写了两种解法。方法一中心扩展每个位置都可以当作回文中心向两边扩展。中心有两种单个字符对应奇数长度和相邻两个字符对应偶数长度。演示代码defexpand(s,left,right):whileleft0andrightlen(s)ands[left]s[right]:left-1right1returns[left1:right]deflongest_palindrome(s):resforiinrange(len(s)):oddexpand(s,i,i)evenexpand(s,i,i1)iflen(odd)len(res):resoddiflen(even)len(res):resevenreturnres运行结果babad返回bab或abacbbd返回bb。要点中心有两种情况所以expand()要分别以(i, i)和(i, i 1)调用两次。方法二动态规划dp[i][j]表示s[i:j1]是不是回文。长度 1 一定是回文长度 2 看两个字符是否相等更长的情况看首尾是否相等且内部dp[i1][j-1]为True。演示代码deflongest_palindrome_dp(s):nlen(s)dp[[False]*nfor_inrange(n)]resforlengthinrange(1,n1):foriinrange(n-length1):jilength-1iflength1:dp[i][j]Trueeliflength2:dp[i][j]s[i]s[j]else:dp[i][j]s[i]s[j]anddp[i1][j-1]ifdp[i][j]andlengthlen(res):ress[i:j1]returnres运行结果和中心扩展一致。踩坑动态规划必须按子串长度从小到大遍历因为dp[i1][j-1]依赖更短的子串。我第一次按i从前往后遍历结果用到了还没计算出来的值。三、复盘第 3 题的两条路先用哈希集合暴力判断再用滑动窗口优化核心都是靠set判断重复第 5 题的两条路中心扩展直观动态规划更套路化两者的时间复杂度都是 O(n²)同一种解法写完再自己对比一遍复杂度理解会更深。结尾留言今天从数组刷到字符串发现每类题都有自己的“套路”。接下来我会继续整理做过的题目把哈希集合、滑动窗口、动态规划这些思路都总结成自己的笔记。