字符串

LeetCode 443 https://leetcode.cn/problems/string-compression/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 为了实现原地压缩，我们可以使用双指针分别标志我们在字符串中读和写的位置。每次当读指针 read 移动到某一段连续相同子串的最右侧，我们就在写指针 write 处依次写入该子串对应的字符和子串长度即可。 在实际代码中，当读指针 read 位于字符串的末尾，或读指针 read 指向的字符不同于下一个字符时，我们就认为读指针 read 位于某一段连续相同子串的最右侧。该子串对应的字符即为读指针 read 指向的字符串。我们使用变量 left 记录该子串的最左侧的位置，这样子串长度即为 read−left+1。 特别地，为了达到 O(1) 空间复杂度，我们需要自行实现将数字转化为字符串写入到原字符串的功能。这里我们采用短除法将子串长度倒序写入原字符串中，然后再将其反转即可。 时间复杂度：O(n)，其中 n 为字符串长度，我们只需要遍历该字符串一次。 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。 ...

LeetCode 344 https://leetcode.cn/problems/reverse-string/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 由于 left+right=n−1 恒成立，所以只需要用一个变量 i 表示 left，n−1−i 就是 right。 根据上面的讨论，循环直到 i=⌊n / 2⌋ 时停止。 时间复杂度：O(n)，其中 n 为 s 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...

LeetCode 71 https://leetcode.cn/problems/simplify-path/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用一个栈存储目录，如果当前字符不是 ‘/’，那么更新 dir，直到遇到 ‘/’。如果 dir 是 “.."，把栈顶目录弹出。如果 dir 不是”."、"..“和空串，添加到栈中。最后使用 ‘/’ 连接目录作为答案。为方便处理，首先在 path 最后添加 ‘/’。 时间复杂度：O(n)，其中 n 是字符串 path 的长度。 空间复杂度：O(n)。我们需要 O(n) 的空间存储 names 中的所有字符串。 ...

Nowcoder 340 https://www.nowcoder.com/practice/6eec992558164276a51d86d71678b300 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题数据范围为小于 10 亿，需要先把数字拆分为亿，万，个三级。对于每个部分，转换一个四位数为中文读法。 时间复杂度：O(1) 空间复杂度：O(1) ...

LeetCode 395 https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题直接使用滑动窗口，当不满足条件时，无法确定应该如何移动窗口，因此需要添加一个参数，count 记录窗口内不同字母的数量。在滑动窗口的过程中，固定右端点，unique 表示窗口内不同字母的数量，valid 表示至少出现了 k 次的字母的数量。当 unique > count 时，需要右移窗口左端点。当 valid == count 时，窗口合法，更新答案。最后遍历 count 的可能值 1 - 26，得到最终的答案。 时间复杂度: O(26∗n) 空间复杂度: O(n) ...

NowCoder 330 https://www.nowcoder.com/practice/c5db069fd9d64e6e9cf5fd68860abcdd 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题类似 LeetCode 415 字符串相加，不过改成了 36 进制。代码类似，只需要将 10 改为 36，以及 36 进制字符与数字的转换。 时间复杂度：O(max(m, n))。 空间复杂度：O(1)。 ...

LeetCode 44 https://leetcode.cn/problems/wildcard-matching/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划，我们用 dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配。状态转移方程为 if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] | dp[i - 1][j]; } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。 空间复杂度：O(mn)，即为存储所有 (m+1)(n+1) 个状态需要的空间。此外，在状态转移方程中，由于 dp[i][j] 只会从 dp[i][..] 以及 dp[i−1][..] 转移而来，因此我们可以使用滚动数组对空间进行优化，即用两个长度为 n+1 的一维数组代替整个二维数组进行状态转移，空间复杂度为 O(n)。 ...

LeetCode 125 https://leetcode.cn/problems/valid-palindrome/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 初始化一左一右两个指针 i=0，j=n−1。其中 n 是 s 的长度。 C++ 判断字符的常用函数如下： 1. 判断字符是否为数字：isdigit(c) 2. 判断字符是否为字母或数字：isalnum(c) 3. 判断字符是否为字母：isalpha(c) 4. 判断字符是否为大写字母：isupper(c) 5. 判断字符是否为小写字母：islower(c) 6. 将大写字母转换为小写：tolower(c) 7. 将小写字母转换为大写：toupper(c) 分类讨论： 如果 s[i] 既不是字母也不是数字，右移左指针，也就是把 i 加一。 如果 s[j] 既不是字母也不是数字，左移右指针，也就是把 j 减一。 否则，如果 s[i] 和 s[j] 转成小写后相等，那么把 i 加一，把 j 减一，继续判断。 否则，s 不是回文串，返回 false。 循环直到 i≥j 为止。最后返回 true。 时间复杂度：O(n)，其中 n 是 s 的长度。 空间复杂度：O(1)。 ...

LeetCode 468 https://leetcode.cn/problems/validate-ip-address/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 模拟题。 我们首先查找给定的字符串 queryIP 中是否包含符号 ‘.’。如果包含，那么我们需要判断其是否为 IPv4 地址；如果不包含，我们则判断其是否为 IPv6 地址。 对于 IPv4 地址而言，它包含 4 个部分，用 ‘.’ 隔开。因此我们可以存储相邻两个 ‘.’ 出现的位置 last 和 cur（当考虑首个部分时，last=−1；当考虑最后一个部分时，cur=n，其中 n 是字符串的长度），那么子串 queryIP[last+1..cur−1] 就对应着一个部分。我们需要判断： 它的长度是否在 [1,3] 之间（虽然这一步没有显式要求，但提前判断可以防止后续计算值时 32 位整数无法表示的情况）； 它是否只包含数字； 它的值是否在 [0,255] 之间； 它是否不包含前导零。具体地，如果它的值为 0，那么该部分只能包含一个 0，即 (cur−1)−(last+1)+1=1；如果它的值不为 0，那么该部分的第一个数字不能为 0，即 queryIP[last+1] 不为 0。 对于 IPv6 地址而言，它包含 8 个部分，用 ‘:’ 隔开。同样地，我们可以存储相邻两个 ‘:’ 出现的位置 last 和 cur，那么子串 queryIP[last+1..cur−1] 就对应着一个部分。我们需要判断： 它的长度是否在 [1,4] 之间； 它是否只包含数字，或者 a-f，或者 A-F； 除了上述情况以外，如果我们无法找到对应数量的部分，那么给定的字符串也不是一个有效的 IP 地址。 时间复杂度：O(n)，其中 n 是字符串 queryIP 的长度。我们只需要遍历字符串常数次。 空间复杂度：O(1)。 ...

LeetCode 14 https://leetcode.cn/problems/longest-common-prefix/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 从左到右遍历 strs 的每一列。 设当前遍历到第 j 列，从上到下遍历这一列的字母。 设当前遍历到第 i 行，即 strs[i][j]。如果 j 等于 strs[i] 的长度，或者 strs[i][j] != strs[0][j]，说明这一列的字母缺失或者不全一样，那么最长公共前缀的长度等于 j，返回 strs[0] 的长为 j 的前缀。 如果没有中途返回，说明所有字符串都有一个等于 strs[0] 的前缀，那么最长公共前缀就是 strs[0]。 时间复杂度：O(nm)，其中 n 为 strs 的长度，m 为 strs 中最短字符串的长度。 空间复杂度：O(1)。返回值不计入。 ...