給定兩個(gè)字符串雷酪，返回兩個(gè)字符串的最長公共子序列，如果不存在公共子序列释涛，返回0加叁。
子序列是指，是由原字符串在不改變相對(duì)順序的情況下刪除某些字符（或不刪除字符后）組成的新字符串唇撬。
動(dòng)態(tài)規(guī)劃
dp[i][j] 表示s1[0, i]和s2[0, j]的最長公共子序列它匕。
- 時(shí)間復(fù)雜度O(mn)，空間復(fù)雜度O(mn)
- Runtime: 152 ms, faster than 38.36%
- Memory Usage: 48.8 MB, less than 85.00%
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
const m = text1.length + 1;
const n = text2.length + 1;
const dp = new Array(m).fill().map(i => Array(n).fill(0));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m - 1][n - 1];
};
