字符串

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)。返回值不计入。 ...

LeetCode 394 https://leetcode.cn/problems/decode-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用双栈法。一个栈存储数字，一个栈存储字符串。当遇到数字时，更新数字，注意数字可能有多位；遇到字母时，加到当前字符串中；遇到 ‘[’ 时，将将当前字符串和数字入栈；遇到 ‘]’ 时，解码，将数字和字符串出栈，将当前字符串重复 k 次加到栈顶字符串后面，将栈顶字符串更新为当前字符串。 时间复杂度：O(S)。 空间复杂度：O(S)。 ...

LeetCode 151 https://leetcode.cn/problems/reverse-words-in-a-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 先翻转整个字符串，再分别翻转每一个单词。 时间复杂度：O(n)，其中 n 为输入字符串的长度。 空间复杂度：O(n)，用来存储字符串分割之后的结果。 ...

LeetCode 8 https://leetcode.cn/problems/string-to-integer-atoi/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是一道比较麻烦的模拟。 跳过前导空格。 检查符号。 读入数字。需要注意检查溢出。32 位 int 的范围是 [-2147483648, 2147483647]。无论是正数还是负数，只要绝对值大于 2147483647，我们就返回 INT_MAX/INT_MIN。对于正数是已经溢出，对于负数则正好是 INT_MIN。判断方式是 ans > INT_MAX / 10 || (ans == INT_MAX / 10 && s[i] > ‘7’)。 时间复杂度：O(n)。 空间复杂度：O(1)。 ...

LeetCode 165 https://leetcode.cn/problems/compare-version-numbers/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用两个指针，遍历两个字符串，直到找到’.’，将每一段的版本号转换为整数，比较两个整数是否相等。整数初始化为 0，以处理这一段版本号缺失的情况。 时间复杂度：O(n+m)，其中 m 是字符串 version1 的长度，n 是字符串 version2 的长度。 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。 ...

LeetCode 5 https://leetcode.cn/problems/longest-palindromic-substring/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是字符串的经典题目，有 3 种做法，分别是动态规划，中心扩展法和马拉车算法。其中前两种做法的时间复杂度为\(O(n^2)\)，马拉车算法的时间复杂度为\(O(n)\)。不过由于马拉车算法较为复杂，在这里使用的是实现较为简单的中心扩展算法。 中心扩展算法就是对于每一个元素，分别讨论子串长度为奇数和偶数的情况，如果子串两端的字符相同，就继续向外扩展。 时间复杂度：\(O(n^2)\)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。 空间复杂度：O(1)。 ...

在 C 语言中，字符串实际上是使用空字符 \0 结尾的一维字符数组。C 标准库提供了一系列对于字符串的操作，大多定义在头文件 <string.h> 中。本文对一些常用的字符串操作进行记录。 ...