下午还在面试别人，晚上就被告知可以开始找工作了。。_

来源：编程网事

大家好，我就是那个在B站讲算法的「华南溜达虎」。

今天看到一位曾经在创维工作过的脉友发帖说，下午还在面试别人，晚上就被告知可以开始找工作了。这顿操作直接把这位脉友给整懵了。

评论区有些人认为楼主下午面试的就是自己的替代品。还有人认为这很正常，很多面试官在招人的时候自己也偷偷投简历。由于这位脉友面试官的身份，更多人不是对他同情，而是幸灾乐祸，有脉友说应该是平时面试挂的人太多导致报的有点快。这位脉友应该面试的时候受过伤，多少带了点情绪在里面。还有脉友开玩笑说，下午听别人自我介绍，晚上给别人介绍自我。这也应了那句，自古评论区出人才。

不少同学对虎哥的视频非常认可，直接成为了原始粉。

言归正传，今天我们来分享一道高频面试题「回文子串」。

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

举个例子：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

思路解析

首先我们可以通过暴力遍历的方式枚举字符串s所有的子串，统计其中回文串的个数，但是时间复杂度太高，这里不再详细的讲解。下面介绍一种中心扩散法。

分两情况来考虑：

回文子串的长度为奇数，这时我们就枚举回文子串所有可能的中心s[i]，0 <= i < s.length，以中心s[i]向两边扩散寻找所有的回文子串。如下图a就是回文串"cbabc"的中心。

回文子串的长度为偶数，这时我们就枚举回文子串所有可能的中心s[i]s[i+1]，0 <= i < s.length - 1，以中心s[i]s[i+1]向两边扩散寻找所有的回文子串。如下图aa就是回文串"cbaabc"的中心。

所以本题的关键是枚举回文子串的中心。

C++代码

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        int s_len = s.length();
        for (int i = 0; i < s_len; ++i) {
            //若回文串长度为奇数,以s[i]为中心向两边扩散寻找以s[i]为中心的所有回文子串
            int left = i, right = i;
            while (left >= 0 && right < s_len && s[left] == s[right]) {
                ++res;
                --left;
                ++right;
            }
            //若回文串长度为偶数，以s[i]s[i+1]为中心向两边扩散寻找以s[i]s[i+1]为中心的所有回文子串
            left = i;
            right = i + 1;
            while (left >= 0 && right < s_len && s[left] == s[right]) {
                ++res;
                --left;
                ++right;
            }
        }
        return res;
    }
};

python代码

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        sLen = len(s)
        for i in range(sLen):
            # 若回文串长度为奇数，以s[i]为中心向两边扩散寻找以s[i]为中心的所有回文子串
            left = i
            right = i
            while left >= 0 and right < sLen and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
            # 若回文串长度为偶数，以s[i]s[i+1]为中心向两边扩散寻找以s[i]s[i+1]为中心的所有回文子串
            left = i
            right = i + 1
            while left >= 0 and right < sLen and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
        return res

复杂度分析

时间复杂度：整个过程会遍历s中每个元素为中心的所有回文子串，所以时间复杂度是O(n2)，其中n是字符串s的长度。

空间复杂度：整个过程只用到几个整型变量，所以空间复杂度为O(1)。

号外

经常使用leetcode会员的同学可以用我的优惠通道啦！

https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解！

今天的分享就到这里，希望大家能有所收获！

特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。