(Leetcode) 1143 - Longest Common Subsequence 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/longest-common-subsequence
dfs를 통한 풀이
답은 대략 다 맞는것 같은데 Time Limit Exceeded 가 발생된다.
class Solution {
int longest = 0;
public int longestCommonSubsequence(String text1, String text2) {
dfs(text1, text2, 0, 0, 0);
return longest;
}
private void dfs(String text1, String text2, int pointer1, int pointer2, int currentMax) {
if (pointer1 == text1.length()) {
return;
}
dfs(text1, text2, pointer1 + 1, pointer2, currentMax); // 그냥 다음 문자로 넘김, 선택하지 않는게 베스트 일 수 있음.
int tempNext = text2.indexOf(text1.charAt(pointer1), pointer2);
if (tempNext != -1) {
if (tempNext < pointer2) {
currentMax = 1;
} else {
currentMax++;
while(pointer1 < text1.length() - 2 && tempNext < text2.length() - 2
&& text1.charAt(pointer1 + 1) == text2.charAt(tempNext + 1)) {
pointer1++;
tempNext++;
currentMax++;
}
}
longest = Math.max(longest, currentMax);
dfs(text1, text2, pointer1 + 1, tempNext + 1, currentMax);
}
}
}
dp를 통한 풀이
아마도 처음으로 접한 2차원 배열을 사용한 DP 문제가 아닐까 싶다.
dp 로 접근해보니 바로 전에 푼 62번 문제와도 유사해진 것 같다.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (text1.charAt(i - 1) == text2.charAt(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[text1.length()][text2.length()];
}
}
TC, SC
시간 복잡도는 O(m * n) 공간 복잡도는 O(m * n) 이다.