最近网上看到一个帖子：华子员工吐槽，感谢公司把他裁了！他从年薪40万的互联网公司，直接降薪到国企25万，虽然少了15万工资，但“没有了绩效压力，996也不见了，甚至成了真正的‘965’”。
算法题：交错字符串
s1，s2 和 s3，判断 s3 是否是由 s1 和 s2 交错拼接而成。交错拼接意味着 s3 中的字符可以从 s1 和 s2 中依次选取，且选取的顺序要保持不变。s1 = "abc"s2 = "def"s3 = "adbcef"
s1 和 s2 中按顺序取字符，最终拼出 s3。dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否可以交错拼接成 s3 的前 i + j 个字符。首先，我们要确保 s1和s2的长度之和正好等于s3的长度。如果不等，直接返回false。然后，我们使用动态规划来填充 dp数组。dp[i][j]只有在以下两种情况之一成立时才为true：
dp[i-1][j]为true且s1[i-1] == s3[i+j-1]，即从s1取一个字符dp[i][j-1]为true且s2[j-1] == s3[i+j-1]，即从s2取一个字符
dp[s1.length()][s2.length()] 就是答案，如果为 true，说明可以交错拼接；否则，不能。public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// 如果s1和s2的长度之和不等于s3的长度，直接返回false
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
// 初始状态，dp[0][0]是true，因为两个空字符串可以交错拼接成空字符串
dp[0][0] = true;
// 填充dp数组
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
}
if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
}
}
}
return dp[s1.length()][s2.length()];
}
}
s1 和 s2 的长度之和是否等于 s3 的长度，这是一个基础的预处理步骤。然后我们创建了一个二维布尔数组 dp，并通过两层循环来填充它。每次检查 dp[i][j] 是否能从 dp[i-1][j] 或 dp[i][j-1] 转移过来，并确保字符匹配。dp[s1.length()][s2.length()] 就是我们要的结果。只要这个值为 true，就说明 s3 可以由 s1 和 s2 交错拼接。m 和 n 分别是 s1 和 s2 的长度。这个算法相较于暴力递归来说，效率提升了很多，避免了重复计算。小总结：
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
