Description

1143. 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 generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

---

1143. 최장 공통 부분 수열

두 문자열 text1과 text2가 주어질 때, 그들의 최장 공통 부분 수열의 길이를 반환하십시오. 공통 부분 수열이 없는 경우 0을 반환합니다.

문자열의 부분 수열은 원본 문자열에서 일부 문자(없을 수도 있음)를 삭제하고 나머지 문자의 상대적인 순서를 변경하지 않고 생성된 새 문자열입니다.

• 예를 들어, "ace"는 "abcde"의 부분 수열입니다.

두 문자열의 공통 부분 수열은 두 문자열에 공통인 부분 수열입니다.

예제 1:

입력: text1 = "abcde", text2 = "ace"
출력: 3
설명: 최장 공통 부분 수열은 "ace"이며 그 길이는 3입니다.

예제 2:

입력: text1 = "abc", text2 = "abc"
출력: 3
설명: 최장 공통 부분 수열은 "abc"이며 그 길이는 3입니다.

예제 3:

입력: text1 = "abc", text2 = "def"
출력: 0
설명: 공통 부분 수열이 없으므로 결과는 0입니다.

제약조건

• 1 <= text1.length, text2.length <= 1000
• text1과 text2은 오직 소문자로 구성되어져 있습니다.

Solution

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i = 1; i < text1.length() + 1; i++) {
            for (int j = 1; j < text2.length() + 1; 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()];
    }
}