Tag Archives: LCS

LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

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 <= 1000
  • 1 <= text2.length <= 1000
  • The input strings consist of lowercase English characters only.

最长公共子序列问题,直接DP,完整代码如下:

class Solution {
public:
	int longestCommonSubsequence(string text1, string text2) {
		int m = text1.size(), n = text2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
				if (text1[i - 1] == text2[j - 1])++c;
				dp[i][j] = max(max(a, b), c);
			}
		}
		return dp[m][n];
	}
};

本代码提交AC,用时92MS。

HDOJ 1159-Common Subsequence

HDOJ 1159-Common Subsequence

Common Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 59402    Accepted Submission(s): 27503

Problem DescriptionA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, …, xm> another sequence Z = <z1, z2, …, zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, …, ik> of indices of X such that for all j = 1,2,…,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab
programming contest 
abcd mnp

Sample Output

4
2
0

SourceSoutheastern Europe 2003
RecommendIgnatius   |   We have carefully selected several similar problems for you:  10871176100310581069


求最长公共子序列。DP模板题,使用一个dp数组即可,用pre记录原来左上角的值。 代码如下,如果要求出一个lcs,参考《算法导论》P225,使用一个二维数组direction记录每个格子最大值来自哪个方向,重构lcs时从右下角不停的往前找。

#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int lcs(const string& a, const string& b)
{
    int n = a.size(), m = b.size();
    if (n == 0 || m == 0)
        return 0;
    vector<int> dp(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int pre = 0;
        for (int j = 1; j <= m; ++j) {
            int cur = 0;
            if (a[i – 1] == b[j – 1])
                cur = pre + 1;
            else
                cur = max(dp[j – 1], dp[j]);
            pre = dp[j];
            dp[j] = cur;
        }
    }
    return dp[m]; // 最大值就是右下角的值
}
void construct_lcs(vector<vector<int> >& direction, const string& a, int i, int j, string& lcs)
{
    if (i == 0 || j == 0)
        return;
    if (direction[i][j] == 3) {
        construct_lcs(direction, a, i – 1, j – 1, lcs);
        lcs += string(1, a[i – 1]); // direction下标1对应a下标0,所以i-1
    }
    else if (direction[i][j] == 2) {
        construct_lcs(direction, a, i – 1, j, lcs);
    }
    else {
        construct_lcs(direction, a, i, j – 1, lcs);
    }
}
string lcs_string(const string& a, const string& b)
{
    int n = a.size(), m = b.size();
    if (n == 0 || m == 0)
        return 0;
    vector<int> dp(m + 1, 0);
    vector<vector<int> > direction(n + 1, vector<int>(m + 1, 0)); // 1:left,2:up,3:diagonal
    for (int i = 1; i <= n; ++i) {
        int pre = 0;
        for (int j = 1; j <= m; ++j) {
            int cur = 0;
            if (a[i – 1] == b[j – 1]) {
                cur = pre + 1;
                direction[i][j] = 3;
            }
            else {
                if (dp[j – 1] > dp[j]) {
                    cur = dp[j – 1];
                    direction[i][j] = 1;
                }
                else {
                    cur = dp[j];
                    direction[i][j] = 2;
                }
            }
            pre = dp[j];
            dp[j] = cur;
        }
    }
    string ans;
    construct_lcs(direction, a, n, m, ans); // 从右下角递归往前找,LCRS P225
    return ans;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    string a, b;
    while (cin >> a >> b) {
        cout << lcs(a, b) << endl;
        //cout << lcs(a, b) << "\t" << lcs_string(a, b) << endl;;
    }
    return 0;
}

本代码提交AC,用时46MS。

LeetCode Delete Operation for Two Strings

LeetCode Delete Operation for Two Strings Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string. Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
  1. The length of given words won’t exceed 500.
  2. Characters in given words can only be lower-case letters.

给定两个字符串,求最少的删除次数,使得两个字符串相等。 这其实就是求两个字符串的最长公共子序列,因为最少的删除次数之后,两个字符串都变成了lcs,则每个字符串删除的次数就是原始长度减去lcs的长度。 代码如下: [cpp] class Solution { private: int lcs(const string& s1, const string& s2) { int n1 = s1.size(), n2 = s2.size(); vector<int> dp1(n2 + 1, 0), dp2(n2 + 1, 0); int ans = 0; for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { if (s1[i – 1] == s2[j – 1])dp2[j] = dp1[j – 1] + 1; else dp2[j] = max(dp1[j], dp2[j – 1]); ans = max(ans, dp2[j]); } dp1.swap(dp2); } return ans; } public: int minDistance(string word1, string word2) { int l = lcs(word1, word2); return word1.size() – l + word2.size() – l; } }; [/cpp] 本代码提交AC,用时52MS。]]>

hihoCoder week 60-1-String Matching Content Length

hihoCoder week 60-1-String Matching Content Length 题目1 : String Matching Content Length 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings. The first restriction here is that every common substring’s length should not be less than 3. For example: strA: abcdefghijklmn strB: ababceghjklmn The matching contents in strA and strB are substrings (“abc”, “jklmn”). Note that though “e” and “gh” are common substrings of strA and strB, they are not matching content because their lengths are less than 3. The second restriction is that the start indexes of all common substrings should be monotone increasing. For example: strA: aaabbbbccc strB: aaacccbbbb The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing. 输入 Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100. 输出 The maximum length of matching contents (the sum of the lengths of the common substrings). 样例输入 abcdefghijklmn ababceghjklmn 样例输出 8


本题在普通的最长公共子序列问题上添加了一个限制条件,构成最长公共子序列的每一个子串长度必须大于等于3。题目中下面这段的含义就是指求的是最长公共子序列,LCS就是从左往右依次扫描找相同的字母,ccc是公共子序列,但不是最长的,因为aaabbbb更长。
The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing.
至于题解,讨论里写得很清楚了,不过要让我自己想还真想不出来。代码实现也很简单,如下: [cpp] #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstdlib> using namespace std; const int kMaxLen = 2105; string a, b; int dp[kMaxLen][kMaxLen][2]; int f[kMaxLen][kMaxLen]; void Init() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { if (a[i] == b[j]) f[i][j] = f[i – 1][j – 1] + 1; else f[i][j] = 0; } } } void Lcs() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { dp[i][j][1] = 0; if (f[i][j] >= 3) { dp[i][j][1] = max(dp[i][j][1], dp[i – 3][j – 3][0] + 3); if (f[i][j]>3) dp[i][j][1] = max(dp[i][j][1], dp[i – 1][j – 1][1] + 1); } dp[i][j][0] = max(dp[i – 1][j][0], max(dp[i][j – 1][0], dp[i][j][1])); } } } int main() { cin >> a >> b; a = " " + a; b = " " + b; Init(); Lcs(); printf("%d\n", dp[a.size() – 1][b.size() – 1][0]); return 0; } [/cpp] 本代码提交AC,用时319MS,内存50MB。]]>