职场杂谈：背调手段进化与LeetCode第5题“最长回文子串”动态规划详解

最近有网友分享了自己在入职前遭遇公司背景调查的经历，HR问得非常详细，而被咨询的前同事竟然也相当配合。这让不少人感慨，如今招聘一个产品经理都需要如此大动干戈吗？这又不是招高管。

回想起我自己求职时也遇到过背调，但当时主要是核查社保记录，核心目的是验证工作履历的真实性，判断你是否真的在那家公司待过，对于个人能力其实无从查起。

背景调查如今在职场中已不新鲜。之前有位前同事，离职后空了半年多，在背调时填了我的联系方式。他提前给我打电话通气，告诉我该怎么回答。结果不到十分钟，HR的电话果真打来了。这种背调，说穿了就是 往好了夸 ，最后他也成功入职。所以啊，在工作中维护好同事关系，有个能“肝胆相照”的伙伴，关键时刻在背调时帮你说上两句好话，确实很重要。

当然，背调也有坑的时候。如果你离职是因为和上级关系闹僵，而背调又要求必须提供领导的联系方式，那结果就可想而知了。

下面这张图展示了一次真实的背调对话，HR询问得非常细致。

对于背调，网友们的看法也是五花八门。有人质疑其必要性和准确性，有人吐槽流程，也有人讨论其合法性边界。

聊完了职场话题，我们切换一下频道，来看一道经典的算法题。这是来自 LeetCode 的第5题：最长回文子串。无论是为了面试求职刷题，还是提升算法能力，这道题都值得深入研究。

问题描述

来源：LeetCode 第5题
难度：中等

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

问题分析

题目要求找出字符串 s 中的最长回文子串。最直观的解法当然是暴力枚举所有子串，然后逐一判断是否为回文，并记录最长的那个。这种方法简单直接，但时间复杂度太高，不适合较长的字符串。

另一种常见思路是“中心扩散法”，以每个字符（或每两个字符中间）为中心，向两边扩展寻找回文。这种方法效率尚可，但仍有优化空间。更高效的解法是著名的“马拉车算法”(Manacher‘s Algorithm)，它能在 O(n) 时间复杂度内解决此问题。

不过，我们今天重点讲解另一种非常经典的解法——动态规划。动态规划的思路清晰，是解决此类区间问题的有力工具。

我们定义二维布尔数组 dp[][]。如果 dp[left][right] 为 true，则表示子串 s[left, right] 是回文子串；如果为 false，则表示不是。

那么，如何判断 dp[left][right] 是否为真呢？一个子串是回文串，需要满足两个核心条件：

1. 子串的首尾字符必须相等，即 s[left] == s[right]。
2. 去掉首尾字符后剩下的部分（即 s[left+1, right-1]）也必须是回文串（或者剩余部分长度很小，天然就是回文）。

具体来说，我们可以按以下规则递推：

1. 如果 s[left] != s[right]，那么 dp[left][right] = false。
2. 如果 s[left] == s[right]，则需要进一步判断：
   • 如果 left == right，即只有一个字符，肯定是回文串。
   • 如果 right - left <= 2，即类似于 "aa" 或 "aba" 的情况，中间最多一个字符，也肯定是回文串。
   • 如果 right - left > 2，那么 dp[left][right] 的值完全取决于 dp[left+1][right-1]。

上述逻辑可以总结为以下递推公式：
dp[left][right] = s[left] == s[right] && dp[left+1][right-1]，并加上上述边界条件。

这里有一个关键点：因为计算 dp[left][right] 时，依赖的是 dp[left+1][right-1]（即左下角的值），所以我们不能按普通的行优先顺序遍历。必须保证在计算 dp[left][right] 时，dp[left+1][right-1] 已经被计算过了。

常见的遍历方式是从左到右一列一列地计算，或者从下到上一行一行地计算。下图展示了一种从下到上的遍历顺序，灰色区域是无效区间（left > right）。

下面，我们给出基于动态规划的Java和C++实现代码。

JAVA 实现

public String longestPalindrome(String s) {
    // start表示最长回文子串开始的位置，为了后面截取。
    // maxLen表示最长回文子串的长度
    int start = 0, maxLen = 1;
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int right = 1; right < length; right++) {
        for (int left = 0; left < right; left++) {
            // 如果两种字符不相同，肯定不能构成回文子串。
            if (s.charAt(left) != s.charAt(right))
                continue;
            // 下面是s[left]和s[right]两个字符相同情况下的判断。
            if (right - left <= 2) {
                // 类似于"a"，"aa"和"aba"，也是回文子串。
                dp[left][right] = true;
            } else {
                // 类似于"a******a"，要判断他是否是回文子串，只需要
                // 判断"******"是否是回文子串即可。
                dp[left][right] = dp[left + 1][right - 1];
            }
            // 如果字符串从left到right是回文子串，保存最长的回文子串。
            if (dp[left][right] && right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
    }
    // 截取最长的回文子串
    return s.substring(start, start + maxLen);
}

C++ 实现

class Solution {
public:
    string longestPalindrome(string s) {
        // start表示最长回文子串开始的位置，为了后面截取。
        // maxLen表示最长回文子串的长度
        int start = 0, maxLen = 1;
        int length = s.size();
        vector<vector<bool>> dp(length, vector<bool>(length, false));
        for (int right = 1; right < length; right++) {
            for (int left = 0; left < right; left++) {
                // 如果两种字符不相同，肯定不能构成回文子串。
                if (s[left] != s[right])
                    continue;
                // 下面是s[left]和s[right]两个字符相同情况下的判断。
                if (right - left <= 2) {
                    // 类似于"a"，"aa"和"aba"，也是回文子串。
                    dp[left][right] = true;
                } else {
                    // 类似于"a******a"，要判断他是否是回文子串，只需要
                    // 判断"******"是否是回文子串即可。
                    dp[left][right] = dp[left + 1][right - 1];
                }
                // 如果字符串从left到right是回文子串，保存最长的回文子串。
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    start = left;
                }
            }
        }
        // 截取最长的回文子串
        return s.substr(start, maxLen);
    }
};

以上就是关于职场背调现象的闲聊以及对LeetCode第5题“最长回文子串”的动态规划解法详解。希望无论是职场经验还是算法解析，都能对你有所启发。如果你想查看更多技术讨论或算法干货，欢迎来云栈社区交流分享。