1143 Longest Common Subsequence
https://leetcode.com/problems/longest-common-subsequence/
solution
字符串头部追加一个空格,以减少边界判断/初始化
除了追加空格外, f[i][j]代表s1的前 i-1 个字符、s2的前 j-1 的字符
时间复杂度:O() 空间复杂度:O()
follow up
注意理解和718. 最长重复子数组的区别
718中dp[i][j]含义是以i-1结尾和j-1结尾的最长重复子数组,如果值不一样,dp仍然是初始值
本题中dp[i][j]含义是长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
总结下来,什么时候dp需要以i/i-1为结尾?根据意义,判断能否转移。需要以结尾的话,状态转移过程中有中断和重新开始
583. Delete Operation for Two Strings
时间复杂度:O() 空间复杂度:O()
时间复杂度:O() 空间复杂度:O()
Last updated