codekofi
← All questions

Longest Common Subsequence

Hard2-D Dynamic Programming

The problem

A subsequence is what remains after deleting some characters and keeping the rest in order.

Return the length of the longest string that is a subsequence of both inputs.

longestCommonSubsequence("abcde", "ace")

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int longestCommonSubsequence(const string& text1, const string& text2) {
2
3 int m = text1.size();
4 int n = text2.size();
5
6 vector<int> prev(n + 1, 0);
7 vector<int> curr(n + 1, 0);
8
9 for (int i = 1; i < m; i++) {
10
11 for (int j = 1; j < n; j++) {
12
13 if (text1[i - 1] == text2[j - 1]) {
14 curr[j] = prev[j - 1] + 1;
15 } else {
16 curr[j] = max(prev[j], curr[j - 1]);
17 }
18 }
19
20 swap(prev, curr);
21 }
22
23 return prev[n];
24}
1int longestCommonSubsequence(const string& text1, const string& text2) {
2
3 int m = text1.size();
4 int n = text2.size();
5
6 vector<int> prev(n + 1, 0);
7 vector<int> curr(n + 1, 0);
8
9 for (int i = 1; i <= m; i++) {
10
11 for (int j = 1; j <= n; j++) {
12
13 if (text1[i - 1] == text2[j - 1]) {
14 curr[j] = prev[j - 1] + 1;
15 } else {
16 curr[j] = max(prev[j], curr[j - 1]);
17 }
18 }
19
20 swap(prev, curr);
21 }
22
23 return prev[n];
24}
1int longestCommonSubsequence(const string& text1, const string& text2) {
2
3 int m = text1.size();
4 int n = text2.size();
5
6 vector<int> prev(n + 1, 0);
7 vector<int> curr(n + 1, 0);
8
9 for (int i = 1; i < m; i++) {
10
11 for (int j = 1; j < n; j++) {
12
13 if (text1[i - 1] == text2[j - 1]) {
14 curr[j] = prev[j] + 1;
15 } else {
16 curr[j] = max(prev[j], curr[j - 1]);
17 }
18 }
19
20 swap(prev, curr);
21 }
22
23 return prev[n];
24}