[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][...