Given two strings str1
and str2
, return the shortest string that has both str1
and str2
as subsequences. If multiple answers exist, you may return any of them.
(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywherefrom T) results in the string S.)
Example 1:
Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a substring of "cabac" because we can delete the first "c". str2 = "cab" is a substring of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.
Note:
1 <= str1.length, str2.length <= 1000
str1
andstr2
consist of lowercase English letters.
Solution: LCS
Find the LCS (longest common sub-sequence) of two strings, and insert unmatched characters into the LCS.
Time complexity: O(mn)
Space complexity: O(mn)
C++
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 |
// Author: Huahua, running time: 16 ms, 15.3 MB class Solution { public: string shortestCommonSupersequence(string str1, string str2) { int l1 = str1.length(); int l2 = str2.length(); vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1)); for (int i = 1; i <= l1; ++i) for (int j = 1; j <= l2; ++j) dp[i][j] = str1[i - 1] == str2[j - 1] ? 1 + dp[i - 1][j - 1] : max(dp[i - 1][j], dp[i][j - 1]); deque<char> ans; while (l1 || l2) { char c; if (l1 == 0) c = str2[--l2]; else if (l2 == 0) c = str1[--l1]; else if (str1[l1 - 1] == str2[l2 - 1]) c = str1[--l1] = str2[--l2]; else if (dp[l1 - 1][l2] == dp[l1][l2]) c = str1[--l1]; else if (dp[l1][l2 - 1] == dp[l1][l2]) c = str2[--l2]; ans.push_front(c); } return {begin(ans), end(ans)}; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment