牛客題霸 [最長(zhǎng)公共子序列] C++題解/答案

題目描述

給定兩個(gè)字符串str1和str2，輸出連個(gè)字符串的最長(zhǎng)公共子序列。如過(guò)最長(zhǎng)公共子序列為空，則輸出-1。

題解：

dp經(jīng)典問(wèn)題

代碼：

class Solution { public:/*** longest common subsequence* @param s1 string字符串 the string* @param s2 string字符串 the string* @return string字符串*/string LCS(string s1, string s2) {// write code hereint len1 = s1.size();int len2 = s2.size();string a=solve(len1,len2,s1,s2);return a;}string solve(int len1,int len2,string s1,string s2){vector<vector<string> > dp(len1 + 1, vector<string>(len2 + 1, ""));string temp,temp1,temp2;for(int i = 1; i <= len1; ++i){for(int j = 1; j <= len2; ++j){if(s1[i - 1] == s2[j - 1]){temp = dp[i - 1][j - 1];temp += s1[i - 1];dp[i][j] = temp;}else{temp1 = dp[i - 1][j];temp2 = dp[i][j - 1];if(temp1.size() > temp2.size()){dp[i][j] = temp1;}else{dp[i][j] = temp2;}}}}if (dp[len1][len2] == "")return "-1";elsereturn dp[len1][len2];} };

總結(jié)

以上是生活随笔為你收集整理的牛客题霸 [最长公共子序列] C++题解/答案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。