1092. Shortest Common Supersequence

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. `1 <= str1.length, str2.length <= 1000`
2. `str1` and `str2` consist of lowercase English letters.

1092. Shortest Common Supersequence
``````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] = (s1[i], i + 1, i, 0);
}
for j in 0..m {
dp[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);
}
``````