字节跳动面试算法题难吗？
如果我们过于爽快地承认失败,就可能使自己发觉不了我们非常接近于正确。——卡尔·波普尔
字节跳动面试的一道算法题：找到给定字符串中最长奇对称子串。
示例：
输入: "babad"
偶对称：abba
奇对称：aba
输出: "bab"
注意: "aba" 也是一个有效答案。这道题是LeetCode第5题的变形，先看一下LeetCode上的第五题，最长回文子串。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例2：
输入: "cbbd"
输出: "bb"中心扩展算法:
先确定中心再向两边延伸，回文串有两种：
- 中心的两个字符是一样的，如"abccba"；
- 中心只有一个字符，如"abcba"。
所以针对两种情况要分别来求：
- 针对第一种，每个字符都可以是中心；
- 针对第二种，必须先找到"cc"，即通过s[i] == s[i - 1]这样的判断找到两个c中的某一个，然后向两边延伸着找。
leetcode代码如下：
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 奇对称字串
int len1 = expandAroundCenter(s, i, i);
// 偶对称字串
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
复杂度分析
- O(n^2)，其中n是字符串的长度。长度为1和2的回文中心分别有n和n−1个，每个回文中心最多会向外扩展O(n)次。
- 空间复杂度：O(1)。
看完这道题，再回到面试题，就是里面的子集，很好解决了。
代码如下：
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len = expandAroundCenter(s, i, i);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
这道题还有其他的解决方法，动态规划（时间复杂度O(n^2)），有个名字叫Manacher的人发明了时间复杂度O(n)的“马拉车“算法，本算法比较复杂。感兴趣的可以自己挑战一下～
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-06-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
