各位观众，欢迎来到今天的“字符串那些事儿”专场！我是你们的字符串老司机，今天咱们不飙车，就聊聊字符串的翻转和最长回文子串这两个有趣的话题。准备好了吗？系好安全带，咱们发车！
第一站：字符串翻转，小菜一碟？
字符串翻转，听起来是不是很简单？确实，很多语言都有内置函数直接搞定。但在 JavaScript 里，咱们得稍微动动手。
方法一：自带反转函数
Array.prototype.reverse
function reverseString(str) {
return str.split("").reverse().join("");
}
console.log(reverseString("hello")); // 输出: olleh这个方法简单粗暴，先把字符串拆成数组，利用数组的 reverse() 方法反转数组，最后再把数组拼回字符串。
优点： 简单易懂，代码量少。
缺点： 效率略低，因为涉及到字符串和数组之间的转换。
方法二：循环大法
function reverseString(str) {
let reversed = "";
for (let i = str.length - 1; i >= 0; i--) {
reversed += str[i];
}
return reversed;
}
console.log(reverseString("world")); // 输出: dlrow这个方法就是老老实实地从字符串的末尾开始遍历，一个字符一个字符地添加到新的字符串中。
优点： 效率相对较高，没有额外的数组操作。
缺点： 代码稍微多一点。
方法三：递归调用
function reverseString(str) {
if (str === "") {
return "";
} else {
return reverseString(str.substr(1)) + str.charAt(0);
}
}
console.log(reverseString("recursion")); // 输出: noisrucer这个方法利用了递归的思想，每次把字符串的第一个字符放到最后，然后递归调用自身处理剩下的字符串。
优点： 代码简洁，体现了递归的思想。
缺点： 递归深度过大可能会导致栈溢出。
性能对比：
| 方法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
reverse() |
简单易懂 | 效率略低，涉及数组转换 | 小规模字符串翻转 |
| 循环 | 效率较高 | 代码稍多 | 大规模字符串翻转，性能敏感 |
| 递归 | 代码简洁，优雅 | 递归深度限制，可能栈溢出 | 仅作演示，不推荐实际使用 |
总结：
字符串翻转虽然简单，但不同的实现方式各有优缺点。选择哪种方法取决于具体的应用场景。对于小规模字符串，reverse() 方法足矣；对于大规模字符串，循环方法更靠谱；而递归方法，除非你想秀一下，否则还是算了吧。
第二站：最长回文子串，烧脑时刻！
好了，热身结束，接下来咱们进入今天的正题：最长回文子串。这是一个经典的字符串问题，也是面试常客。
什么是回文串？
回文串就是正着读和倒着读都一样的字符串。比如："aba"、"level"、"madam"。
什么是子串？
子串就是原字符串中连续的一段。比如："hello" 的子串有 "he"、"ell"、"lo" 等等。
最长回文子串，顾名思义，就是在一个字符串中找到最长的回文子串。
解法一：暴力破解，简单粗暴
最简单的思路就是穷举所有可能的子串，然后判断每个子串是否是回文串，并记录下最长的回文子串。
function longestPalindrome(str) {
let longest = "";
for (let i = 0; i < str.length; i++) {
for (let j = i; j < str.length; j++) {
const sub = str.substring(i, j + 1);
if (isPalindrome(sub) && sub.length > longest.length) {
longest = sub;
}
}
}
return longest;
}
function isPalindrome(str) {
return str === str.split("").reverse().join("");
}
console.log(longestPalindrome("babad")); // 输出: bab 或 aba
console.log(longestPalindrome("cbbd")); // 输出: bb优点： 思路简单，容易理解。
缺点： 效率极低，时间复杂度是 O(n^3)，其中 n 是字符串的长度。这个复杂度简直让人绝望！
解法二：动态规划，空间换时间
动态规划是一种常用的优化算法的技巧。
- 定义状态：
dp[i][j]表示字符串str从索引i到j的子串是否是回文串。 - 状态转移方程：
dp[i][i] = true(单个字符肯定是回文串)dp[i][i+1] = (str[i] == str[i+1])(相邻字符是否相等)dp[i][j] = (str[i] == str[j] && dp[i+1][j-1])(如果str[i]和str[j]相等，并且dp[i+1][j-1]是回文串，那么dp[i][j]也是回文串)
- 初始化：
dp数组初始化为false。 - 遍历顺序： 从长度较短的子串开始计算，逐渐扩展到长度较长的子串。
function longestPalindrome(str) {
const n = str.length;
const dp = Array(n).fill(null).map(() => Array(n).fill(false));
let longest = "";
for (let len = 1; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (str[i] === str[j] && (len <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (len > longest.length) {
longest = str.substring(i, j + 1);
}
}
}
}
return longest;
}
console.log(longestPalindrome("babad")); // 输出: bab 或 aba
console.log(longestPalindrome("cbbd")); // 输出: bb优点： 效率比暴力破解高很多，时间复杂度是 O(n^2)，空间复杂度也是 O(n^2)。
缺点： 需要额外的空间来存储 dp 数组。
解法三：中心扩展算法，简单高效
中心扩展算法的思想是，从字符串的每个字符或者每两个字符的中间位置开始，向两边扩展，直到遇到不是回文串的情况。
function longestPalindrome(str) {
let longest = "";
for (let i = 0; i < str.length; i++) {
// 以 str[i] 为中心扩展
const len1 = expandAroundCenter(str, i, i);
// 以 str[i] 和 str[i+1] 为中心扩展
const len2 = expandAroundCenter(str, i, i + 1);
const len = Math.max(len1, len2);
if (len > longest.length) {
const start = i - Math.floor((len - 1) / 2);
longest = str.substring(start, start + len);
}
}
return longest;
}
function expandAroundCenter(str, left, right) {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return right - left - 1;
}
console.log(longestPalindrome("babad")); // 输出: bab 或 aba
console.log(longestPalindrome("cbbd")); // 输出: bb优点： 效率高，时间复杂度是 O(n^2)，空间复杂度是 O(1)。
缺点： 代码稍微复杂一点。
解法四：Manacher 算法，终极神器
Manacher 算法是一种专门用于解决最长回文子串问题的线性时间复杂度的算法。它利用了回文串的对称性，避免了重复计算。
这个算法比较复杂，涉及到一些比较巧妙的优化技巧，这里就不展开讲解了，感兴趣的同学可以自行搜索学习。
性能对比：
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|
| 暴力破解 | O(n^3) | O(1) | 简单易懂 | 效率极低 | 仅作演示，不推荐实际使用 |
| 动态规划 | O(n^2) | O(n^2) | 效率较高 | 需要额外的空间存储 dp 数组 |
对空间要求不高的场景 |
| 中心扩展 | O(n^2) | O(1) | 效率高，空间复杂度低 | 代码稍微复杂一点 | 大部分场景 |
| Manacher | O(n) | O(n) | 效率最高 | 算法复杂，理解难度大 | 对性能要求极高的场景，需要深入理解算法 |
总结：
最长回文子串问题是一个经典的字符串问题，有很多种解法。不同的解法各有优缺点，选择哪种方法取决于具体的应用场景。
- 如果对效率要求不高，可以选择暴力破解或者动态规划。
- 如果对效率有一定要求，可以选择中心扩展算法。
- 如果对效率要求极高，可以选择 Manacher 算法。
练习题：
- 给定一个字符串，判断它是否是回文串。
- 给定一个字符串，找到所有回文子串。
- 实现 Manacher 算法。
结语：
好了，今天的“字符串那些事儿”就到这里了。希望通过今天的讲解，大家对字符串的翻转和最长回文子串有了更深入的理解。记住，编程就像开车，熟能生巧，多练习才能成为真正的老司机！
感谢大家的观看，我们下期再见！