###### tags: `leetcode` `medium` `String` `Dynamic Programming`
# [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/description/)

## Description

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.

## Examples
### 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 \leq text1.length, text2.length \leq 1000$
- `text1` and `text2` consist of only lowercase English characters.

## Code

#define MAX(x, y) ( ((x)>(y)) ? (x) : (y))
int longestCommonSubsequence(char * text1, char * text2){
    int length1 = strlen(text1), length2 = strlen(text2);
    int **lcs = malloc((length1 + 1) * sizeof(int*));
    for(int i = 0 ; i <= length1 ; i++)
        lcs[i] = calloc((length2 + 1), sizeof(int));

    for(int row = 1 ; row <= length1 ; row++){
        for(int col = 1 ; col <= length2 ; col++){
            if(text1[row - 1] == text2[col - 1])
                lcs[row][col] = lcs[row - 1][col - 1]+1;
            else
                lcs[row][col] = MAX(lcs[row - 1][col], lcs[row][col - 1]);
        }
    }
    return lcs[length1][length2];
};

## Complexity

|Space |Time |
|- |- |
|$O(length_1*length_2)$|$O(length_1*length_2)$|

- $length_i$: length of input $text_i$

## Result

- Runtime: 12 ms, 89.58%
- Memory: 12.2 MB, 19.58%