仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

最长公共子序列\串

发表于 更新于 分类于 ，
本文字数： 2.5k 阅读时长 ≈ 2 分钟

【道德经·第二十一章】 孔德之容，惟道是从。道之为物，惟恍惟惚。惚兮恍兮，其中有象；恍兮惚兮，其中有物。窈兮冥兮，其中有精，其精甚真，其中有信，自今及古，其名不去，以阅众甫。

1143. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > choice;
string path;
int lcs(string& s1, string& s2, int m, int n) {
    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
    choice.resize(m+1, vector<int>(n+1));
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                choice[i][j] = 1;
            } else if(dp[i-1][j] >= dp[i][j-1]) {
                dp[i][j] = dp[i-1][j];
                choice[i][j] = 2;
            } else {
                dp[i][j] = dp[i][j-1];
                choice[i][j] = 3;
            }
        }
    }
    
    return dp[m][n];
}

void findPath(vector<vector<int> >& choice, string& s, int i, int j) {
    if(i==0 || j==0) return;

    if(choice[i][j] == 1){
        findPath(choice, s, i-1, j-1);
        path.push_back(s[i-1]);
    } else if(choice[i][j] == 2) {
        findPath(choice, s, i-1, j);
    } else {
        findPath(choice, s, i, j-1);
    }
}

int main() {
    string s1 = "gbabcdef", s2 = "gaczef";
    
    int m = s1.size();
    int n = s2.size();
    int x = lcs(s1, s2, m, n);
    printf("length of lcs: %d\n", x);
    
    findPath(choice, s1, m, n);
    cout << "lsc: " << path << "\n";
    system("pause");
    return 0;
}

上述解法需要一个m*n的choice矩阵保存状态，实际上可进一步优化，不使用choice而是根据dp[i][j]、dp[i-1][j-1]、dp[i-1][j]以及dp[i-1][j-1]之间的大小关系直接进行路径逆推，下面是更优解法：

findPath更优解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void findPath(vector<vector<int>>& dp, int m, int n, string& a, string& b) {
    int i = m, j = n;
    string ans(dp[m][n], ' ');
    int index = ans.length() - 1;

    while(index >= 0) {
        if(n > 0 && dp[m][n] == dp[m][n-1]) {
            n--;
        } else if(m > 0 && dp[m][n] == dp[m-1][n]) {
            m--;
        } else {
            ans[index--] = a[m-1];
            m--;
            n--;
        }
    }
    cout<<ans;
}

BM66 最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串。题目保证str1和str2的最长公共子串存在且唯一。

示例1

1
2
输入："1AB2345CD","12345EF"
返回值："2345"

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
string LCS(string str1, string str2) {
    // write code here
    int n = str1.size();
    int m = str2.size();

    vector<vector<int> > dp(n+1, vector<int>(m+1, 0));

    int pos = 0, mx = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = 0;
            }
            
            if(dp[i][j] > mx) {
                mx = dp[i][j];
                pos = i-1;
            }
        }
    }

    return str1.substr(pos-mx+1, mx);

}

位我上者，灿烂星空；道德律令，在我心中。