✉️문제
https://leetcode.com/problems/longest-common-subsequence/description/
Longest Common Subsequence - LeetCode
Can you solve this real interview question? Longest Common Subsequence - Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string genera
leetcode.com
🗝 문제풀이
2차원 배열을 사용하는 기본적인 다이나믹 프로그래밍 문제이다.
시간 복잡도 : O(N^2)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dy = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
dy[i][j] = dy[i - 1][j - 1] + 1;
} else {
dy[i][j] = Math.max(dy[i - 1][j], dy[i][j - 1]);
}
}
}
return dy[n][m];
}
}