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 anywhere from T) results in the string S.)
Example 1:
Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence 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 <= 1000str1 and str2 consist of lowercase English letters.struct Solution;
impl Solution {
fn shortest_common_supersequence(str1: String, str2: String) -> String {
let s1: Vec<char> = str1.chars().collect();
let s2: Vec<char> = str2.chars().collect();
let n = s1.len();
let m = s2.len();
let mut dp = vec![vec![(' ', 0, std::usize::MAX, std::usize::MAX); m + 1]; n + 1];
for i in 0..n {
dp[i + 1][0] = (s1[i], i + 1, i, 0);
}
for j in 0..m {
dp[0][j + 1] = (s2[j], j + 1, 0, j);
}
for i in 0..n {
for j in 0..m {
if s1[i] == s2[j] {
dp[i + 1][j + 1] = (s1[i], dp[i][j].1 + 1, i, j);
} else {
if dp[i][j + 1].1 < dp[i + 1][j].1 {
dp[i + 1][j + 1] = (s1[i], dp[i][j + 1].1 + 1, i, j + 1);
} else {
dp[i + 1][j + 1] = (s2[j], dp[i + 1][j].1 + 1, i + 1, j);
}
}
}
}
let mut path = vec![];
let mut i = n;
let mut j = m;
while dp[i][j].0 != ' ' {
path.push(dp[i][j].0);
let next = dp[i][j];
i = next.2;
j = next.3;
}
path.into_iter().rev().collect()
}
}
#[test]
fn test() {
let str1 = "abac".to_string();
let str2 = "cab".to_string();
let res = "cabac".to_string();
assert_eq!(Solution::shortest_common_supersequence(str1, str2), res);
}