# 1143. Longest Common Subsequence

![](/files/-MedZkJ3TugYT_A-hRyL)

![](/files/-MedZnMkiWnG3RlV3SQp)

Refer to labulado's one:

<https://github.com/jiajunhua/labuladong-fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.md>

## DFS

關鍵 ->&#x20;

lcs 當有相同的字時, dp(i-1,j-1) + 1

不相同時 可能是 max(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)),   因為取最大 所以 dp(i-1, j-1) 效果不好 可以忽略

一路從尾巴 倒推回頭(-1 是終止條件)

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return dp(text1, text2, text1.length()-1, text2.length()-1);
    }
    private int dp(String text1, String text2, int i, int j) {
        if (i == -1 || j == -1) {
            return 0;
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            return dp(text1, text2, i-1, j-1) + 1;
        } else {
            return Math.max(dp(text1, text2, i-1, j), dp(text1, text2, i, j-1));
        }
    }
}
```

## Memo + DFS

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        return dp(text1, text2, m-1, n-1, new Integer[m][n]);
    }
    private int dp(String text1, String text2, int i, int j, Integer[][] memo) {
        if (i == -1 || j == -1) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            return memo[i][j] = dp(text1, text2, i-1, j-1, memo) + 1;
        } else {
            return memo[i][j] = Math.max(dp(text1, text2, i-1, j, memo), dp(text1, text2, i, j-1, memo));
        }
    }
}
```

### DFS+memo, from 0, 0

```java
    private int LCS(String word1, String word2) {
        return dp(word1, word2, 0, 0, new Integer[word1.length()+1][word2.length()+1]);
    }
    private int dp(String word1, String word2, int i, int j, Integer[][] memo) {
        if (i < word1.length() && j < word2.length()) {
            if (i == word1.length() && j == word2.length()) {
                return 0;
            }
            if (memo[i][j] != null) {
                return memo[i][j];
            }
            if ( word1.charAt(i) == word2.charAt(j)) {
                return memo[i][j] = dp(word1, word2, i+1, j+1, memo)+1;
            } else {
                return memo[i][j] = Math.max( 
                    dp(word1, word2, i, j+1, memo), 
                    dp(word1, word2, i+1, j, memo)
                );
            }
        }
        return 0;
    }
    private int max(int i, int j, int k) {
        return Math.max(Math.max(i, j),k);
    }
```

所以 dp table 存的就會是

the length of longest common subsequence of A\[i] and B\[j]

time: O(mn)

space: O(mn)

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int dp[][] = new int[m+1][n+1];
        
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+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][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
}
```

## new way

if we add in string , more "" in the front, the index become normal i, j

<figure><img src="/files/PV49JkaE7mW4a2tkdTll" alt=""><figcaption></figcaption></figure>

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        text1 = "#" + text1;
        text2 = "#" + text2;
        
        int dp[][] = new int[m+1][n+1];
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    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][n];
    }
}
```

## compressed to 1d

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        text1 = "#" + text1;
        text2 = "#" + text2;
        
        int dp[] = new int[n+1];
        
        dp[0] = 0;
        
        for (int i = 1; i <= m; i++) {
            int pre = 0;
            for (int j = 1; j <= n; j++) {
                int cur = dp[j];
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[j] = pre + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                pre = cur;
            }
        }
        return dp[n];
    }
}
```

## buttom up

```python
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]
        
        for i in range(len(text1)-1, -1, -1):
            for j in range(len(text2)-1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])
        return dp[0][0]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/pattern-matching-dp/1143.-longest-common-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.