Wnma's Blogs
0%

Leetcode 字符串刷题记录

发表于 更新于 分类于

字符串刷题分类

滑动窗口

3. 无重复字符的最长子串

从左向右滑，需要一个数据结构（A）记录已经遍历的字符，还有一个变量（B）记录最大长度

注：每次不需要从头开始，而是可以从重复那个字符的后一个开始，所以A需要记录一下索引

KMP

动态规划

5. 最长回文子串

两个指针从两头开始，所以需要二维DP，元素是bool判断

97. 交错字符串

两个字符串组成新的字符串，二维DP，元素是bool判断

139. 单词拆分

单词数组，一个一个单词拼接，组成最后单词，一维DP，元素是bool判断

516. 最长回文子序列

回文，需要两个指针，二维DP，从i到j组成回文的长度，元素是长度，最小长度为1，相等+2

474. 一和零

字符串数组，组成数量限制（两个限制），所以限制需要二个维度，数组作为最外层那个维度，元素是个数，最小为0

583. 两个字符串的删除操作

两个字符串，两个维度，删除次数，初始情况，删除个数为字符串长度。

647. 回文子串

回文，二维DP，元素是bool判断，统计True个数

1143. 最长公共子序列

两个字符串，二维DP，长度

1871. 跳跃游戏 VII

能否到达终点，一维DP，反向思考，能否到达该点，所以元素为bool。+前缀和优化时间

1
2
3
4
5
6
7
8
9
10
# 回文串
dp = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = True
    # 从i到j是否组成回文串
    for i in range(n-1)[::-1]:
        for j in range(i+1, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):
                dp[i][j] = True

双指针

424. 替换后的最长重复字符

枚举右端点，如果没超过限制就继续移动右指针，否则移动左指针

栈

PASS

字典树

PASS

模拟/深搜

PASS