1143. Longest Common Subsequence
# Medium
Very similar to #72, two-sequence DP problem
Subsequence: 子序列,可以跳着来
Substring: 子串,必须元素连续着
Solution:
Initialize
maxCommon[i][j]
, which means longest common substring betweentext1[:i]
andtext2[:j]
. Empty element is necessarily neededThree cases:
maxCommon[i-1][j]
. eg,abc+d
andace
maxCommon[i][j-1]
. eg,abc
andac+d
If
text1[i] = text2[j]
, thenmaxCommon[i][j] + 1
common char. eg,abc+d
andace+d
Compare to assign biggest number to
maxCommon[i][j]
Last updated