点击下方“前端开发爱好者”，选择“设为星标”
第一时间关注技术干货！
哈喽，大家好，我是 xy👨🏻💻。在前端开发的面试中，算法和数据结构的问题是常见的挑战！
面经
前段时间，我一直忙于找工作，刷面试题成为了我的日常。
在众多的面试中，小米的面试给我留下了深刻的印象。
特别是在二面过程中，我遇到了一个非常经典的面试题，让我至今记忆犹新。
今天，我就在这里分享给大家，希望能帮助到同样在求职路上的你。
问题描述
面试官给了我一个字符串处理的问题：
给定一个字符串
str，找到str中最长的回文子串。
并且要求我提供两种解决方案！
示例
输入：
str = "ababc"
输出："aba"或"bab"（两者都是最长回文子串）输入：
str = "abbc"
输出："bb"
方法一：循环遍历法
思路
循环遍历法的基本思想是检查字符串中所有可能的子串，判断它们是否为回文。具体步骤如下：
遍历字符串，对于每个起始位置 i，从i开始向后遍历，尝试所有可能的子串。对于每个子串，使用 isPalindrome函数检查是否为回文。如果是回文，并且长度大于当前记录的最长回文子串，则更新最长回文子串。
代码实现
function longestPalindrome(str) {
let longstr = ""; // 记录最长回文串
let nowstr = ""; // 记录当前回文串
for (let i = 0; i < str.length; i++) {
nowstr = ""; // 每次新的一轮开始时，将临时记录回文串的变量清空
for (let j = i; j < str.length; j++) {
nowstr += str.charAt(j); // 逐个增加字符串的长度
if (isPalindrome(nowstr) && nowstr.length > longstr.length) {
longstr = nowstr; // 更新回文串
}
}
}
return longstr; // 返回最终的最长的回文串
}
function isPalindrome(str) { // 判断是否为回文串
return str === str.split("").reverse().join("");
}
方法二：中心查找法
思路
中心查找法的核心思想是从一个中心点向两边扩展，检查回文。
这种方法需要考虑两种情况：单个字符作为中心和两个字符作为中心。
具体步骤如下：
对于字符串中的每个位置 i，分别考虑i和i+1作为中心点，使用search函数扩展回文子串。search函数通过比较中心点两侧的字符，不断扩展回文子串，直到不再相等。记录并更新最长回文子串的起始和结束位置。 最后，根据起始和结束位置，从原字符串中提取最长回文子串。
代码实现
// 中心查找函数
function search(str, l, r) {
let left = l;
let right = r;
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return right - left - 1;
}
// 主函数
function longestPalindrome(str) {
var start = 0, end = 0;
for (let i = 0; i < str.length; i++) {
let len1 = search(str, i, i); // 奇数长度的回文
let len2 = search(str, i, i + 1); // 偶数长度的回文
let len = Math.max(len1, len2);
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return str.slice(start, end + 1);
};
总结
在小米的前端二面中，掌握如何高效地解决算法问题是非常重要的。
通过上述两种方法，我们不仅可以找到字符串中的最长回文子串，还可以深入理解 JavaScript 中的字符串操作和算法优化。
如果大家还有其它解法，欢迎在评论区聊一聊👏
公众号：前端开发爱好者 专注分享 web 前端相关技术文章、视频教程资源、热点资讯等，如果喜欢我的分享，给 🐟🐟 点一个赞 👍 或者 ➕关注 都是对我最大的支持。
点击上方“前端开发爱好者”，选择“设为星标” 第一时间关注技术干货！
