几道常见的字符串算法题

作者：wwwxmu 原文地址：<https://www.weiweiblog.cn/13string/ 1. KMP 算法 谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n)，而空间复杂度也只有 O(m)。因为 “暴力搜索” 的方法会反复回溯主串，导致效率低下，而 KMP 算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。 具体算法细节请参考： 从头到尾彻底理解 KMP: 如何更好的理解和掌握 KMP 算法? KMP 算法详细解析 图解 KMP 算法 汪都能听懂的 KMP 字符串匹配算法【双语字幕】 KMP 字符串匹配算法 1 除此之外，再来了解一下 BM 算法！ BM 算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。 《字符串匹配的 KMP 算法》：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt\ algorithm.html 2. 替换空格 剑指 offer：请实现一个函数，将一个字符串中的每个空格替换成 "%20"。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。 这里我提供了两种方法：① 常规方法；② 利用 API 解决。 对于替换固定字符（比如空格）的情况，第二种方法其实可以使用 方法替换，性能更好！ 3. 最长公共前缀 Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 示例 1： 示例 2： 思路很简单！先利用 为数组排序，再将数组第一个元素和最后一个元素的字符从前往后对比即可！ 4. 回文串 4.1. 最长回文串 LeetCode: 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 不能当做一个回文字符串。注意：假设字符串的长度不会超过 1010。 回文串：“回文串” 是一个正读和反读都一样的字符串，比如 "level" 或者 "noon" 等等就是回文串。——百度百科 地址：https://baike.baidu.com/item/回文串/1274921?fr=aladdin 示例 1： 我们上面已经知道了什么是回文串？现在我们考虑一下可以构成回文串的两种情况： 字符出现次数为双数的组合 字符出现次数为偶数的组合+单个字符中出现次数最多且为奇数次的字符 （参见 issue665 ） 统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如 "abcba"，所以如果最后有字母落单，总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在 hashset 中，如果不在就加进去，如果在就让 count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。 4.2. 验证回文串 LeetCode: 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。 示例 1： 示例 2： 4.3. 最长回文子串 LeetCode: 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 示例 2： 以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。 4.4. 最长回文子序列 LeetCode: 最长回文子序列 给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。 最长回文子序列和上一题最长回文子串的区别是，子串是字符串中连续的一个序列，而子序列是字符串中保持相对位置的字符序列，例如，"bbbb" 可以是字符串 "bbbab" 的子序列但不是子串。 给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。 示例 1： 一个可能的最长回文子序列为 "bbbb"。 示例 2： 一个可能的最长回文子序列为 "bb"。 动态规划： 5. 括号匹配深度 爱奇艺 2018 秋招 Java： 一个合法的括号匹配序列有以下定义： 1. 空串 "" 是一个合法的括号匹配序列 2. 如果 "X" 和 "Y" 都是合法的括号匹配序列，"XY" 也是一个合法的括号匹配序列 3. 如果 "X" 是一个合法的括号匹配序列，那么 "(X)" 也是一个合法的括号匹配序列 4. 每个合法的括号序列都可以由以上规则生成。 例如：""，"()"，"()()"，"((()))" 都是合法的括号序列。 对于一个合法的括号序列我们又有以下定义它的深度： 1. 空串 "" 的深度是 0 2. 如果字符串 "X" 的深度是 x，字符串 "Y" 的深度是 y，那么字符串 "XY" 的深度为 max(x, y) 3. 如果 "X" 的深度是 x，那么字符串 "(X)" 的深度是 x+1 例如："()()()" 的深度是 1，"((()))" 的深度是 3。牛牛现在给你一个合法的括号序列，需要你计算出其深度。 示例： 代码如下： 6. 把字符串转换成整数 剑指 offer: 将一个字符串转换成一个整数（实现 的功能，但是 string 不符合数字要求时返回 0），要求不能使用字符串转换整数的库函数。数值为 0 或者字符串不是一个合法的数值则返回 0。 面试复盘重点 字符串题看起来杂，实际常见模板并不多：哈希计数、双指针、滑动窗口、KMP、回文、栈模拟。 | 题型 | 常用方法 | 代表题 | | | | | | 字符计数 | 数组或哈希表 | 有效的字母异位词、字母异位词分组 | | 子串问题 | 滑动窗口 | 最长无重复子串、最小覆盖子串 | | 回文问题 | 双指针、中心扩展、DP | 验证回文串、最长回文子串 | | 字符串匹配 | KMP、哈希 | 实现 | | 括号和编码 | 栈 | 有效的括号、字符串解码 | | 数字转换 | 模拟 | 字符串转换整数 | 处理字符串题时可以先问 3 个问题： 1. 题目关心的是子串还是子序列？子串连续，子序列不要求连续。 2. 字符集范围有多大？只有小写字母时，数组计数比哈希表更直接。 3. 是否需要处理溢出、空串、空格、符号位这类边界？ 几个易错点： Java 中 不可变，频繁拼接建议使用 。 处理 Unicode 字符时可能不够，普通算法题多数只考 ASCII 或小写字母。 回文子串和回文子序列不是一类题，前者常用中心扩展，后者常用 DP。 KMP 面试中通常不要求从零推导 数组的手工计算过程，但要理解它的作用是跳过已匹配前缀，避免重复匹配。 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。