[LintCode] Longest Common Subsequence/substring 最常公共子序列 / 子串

ssGiven two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Have you met this question in a real interview? 

Yes

Clarification

What's the definition of Longest Common Subsequence?

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://baike.baidu.com/view/2020307.htm

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

動態規劃中的經典題目 - 最常公共子序列

子序列的意思是 可以不連續的子字串 例如 ABCD 的子序列可以是 ACD

那麼最常公共子序列可以用來幹嘛勒? Wiki 說,

It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

題目解說, https://www.youtube.com/watch?v=NnD96abizww

用二維陣列 處理

比對兩字串的字符 如果一樣 q[i][j] = q[i][j] + 1 

如果不一樣 q[i][j] = max (q[i-1][j], q[i][j+1])

 

附上 最大公共子串

因為是 子串 所以要判斷的是連續的

一樣用二維陣列 處理

比對兩字串的字符 如果一樣 q[i][j] = q[i][j] + 1 

如果不一樣 q[i][j] = 0

用一個變數 res 存 max(q[i][j])