Robin's Blog

对于两个字符串求子序列的问题，都是用两个指针 i 和 j 分别在两个字符串上移动，大概率是动态规划思路。 labuladong-最长公共子序列 相关题目1143. 最长公共子序列 583. 两个字符串的删除操作 712. 两个字符串的最小ASCII删除和 思路定义dp(s1, i, s2, j)为s1[i...] 和 s2[j...]的最长公共子序列长度 goal: dp(s1, 0, s2, 0) 从零开始的最长公共子序列长度 base case: i == len(s1) 或 j == len(s2) 由于相当于没有string，所以最长公共子序列长度为0 状态转移： 在选的情况下，即charAt[i] == charAt[j]时，状态转移： 在不选的情况下可以从三种情况转移： 但是其实只有情况一和情况二，因为情况三被情况一cover了 1143. 最长公共子序列模板题 代码： 自顶向下的递归解法： 123456789101112131415161718192021222324252627282930class Solution { String text1, tex ...

记录下databricks的面试