Shortest common supersequence

String Dynamic Programming

61.8% acceptance

Feb 25, 2026

5907

101

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them. A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_common_supersequence(str1: String, str2: String) -> String {
    let s1 = str1.as_bytes();
    let s2 = str2.as_bytes();
    let (m, n) = (s1.len(), s2.len());
    let mut dp = vec![vec![0usize; n + 1]; m + 1];
    for i in 1..=m { for j in 1..=n {
      dp[i][j] = if s1[i-1] == s2[j-1] { dp[i-1][j-1] + 1 } else { dp[i-1][j].max(dp[i][j-1]) };
    }}
    let mut res = vec![];
    let (mut i, mut j) = (m, n);
    while i > 0 && j > 0 {
      if s1[i-1] == s2[j-1] { res.push(s1[i-1]); i -= 1; j -= 1; }
      else if dp[i-1][j] >= dp[i][j-1] { res.push(s1[i-1]); i -= 1; }
      else { res.push(s2[j-1]); j -= 1; }
    }
    while i > 0 { res.push(s1[i-1]); i -= 1; }
    while j > 0 { res.push(s2[j-1]); j -= 1; }
    res.reverse();
    String::from_utf8(res).unwrap()
  }
}