<p>Given two strings <code>text1</code> and <code>text2</code>, return <em>the length of their longest <strong>common subsequence</strong>. </em>If there is no <strong>common subsequence</strong>, return <code>0</code>.</p>

<p>A <strong>subsequence</strong> 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.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>A <strong>common subsequence</strong> of two strings is a subsequence that is common to both strings.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abcde&quot;, text2 = &quot;ace&quot; 
<strong>Output:</strong> 3  
<strong>Explanation:</strong> The longest common subsequence is &quot;ace&quot; and its length is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abc&quot;, text2 = &quot;abc&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest common subsequence is &quot;abc&quot; and its length is 3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abc&quot;, text2 = &quot;def&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no such common subsequence, so the result is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text1.length, text2.length &lt;= 1000</code></li>
	<li><code>text1</code> and <code>text2</code> consist of only lowercase English characters.</li>
</ul>

const int N = 1002;
int dp[N][N] = {-1};
class Solution {
public:
    int calc(string& s1, string& s2, int i, int j) {
         //cout << "i: "<<i << " j: "<<j <<endl;
        if (i >= s1.size() || j >= s2.size()) return 0;
        if (dp[i][j]!=-1)return dp[i][j];
        //cout << "new" <<endl;
        char c = s1[i];
        int k = j;
        while(s2[k]!= c && k < s2.size()) {
            k++;
        }
        int ans1 = 0;
        int ans2 = 0;
        if (k < s2.size()) {
            //cout << " i = " << i << " j = " << j << " k = " << k <<endl;

            ans1 =  1 + calc(s1, s2, i+1, k+1);
        }
        ans2 = calc(s1, s2, i+1, j);
        dp[i][j] = max(ans1, ans2);
        return dp[i][j];
    }

    int longestCommonSubsequence(string text1, string text2) {
        for (int i = 0; i < text1.size(); i++) {
            for (int j = 0; j < text2.size(); j++) {
                dp[i][j] = -1;
            }
        }
        return calc(text1, text2, 0, 0);
    }
};
10188