Question

1092. Shortest Common Supersequence

中文文档

Description

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.

 

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.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

 

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

Solutions

Solution 1

class Solution:
  def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
    m, n = len(str1), len(str2)
    f = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if str1[i - 1] == str2[j - 1]:
          f[i][j] = f[i - 1][j - 1] + 1
        else:
          f[i][j] = max(f[i - 1][j], f[i][j - 1])
    ans = []
    i, j = m, n
    while i or j:
      if i == 0:
        j -= 1
        ans.append(str2[j])
      elif j == 0:
        i -= 1
        ans.append(str1[i])
      else:
        if f[i][j] == f[i - 1][j]:
          i -= 1
          ans.append(str1[i])
        elif f[i][j] == f[i][j - 1]:
          j -= 1
          ans.append(str2[j])
        else:
          i, j = i - 1, j - 1
          ans.append(str1[i])
    return ''.join(ans[::-1])

class Solution {
  public String shortestCommonSupersequence(String str1, String str2) {
    int m = str1.length(), n = str2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
          f[i][j] = f[i - 1][j - 1] + 1;
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
        }
      }
    }
    int i = m, j = n;
    StringBuilder ans = new StringBuilder();
    while (i > 0 || j > 0) {
      if (i == 0) {
        ans.append(str2.charAt(--j));
      } else if (j == 0) {
        ans.append(str1.charAt(--i));
      } else {
        if (f[i][j] == f[i - 1][j]) {
          ans.append(str1.charAt(--i));
        } else if (f[i][j] == f[i][j - 1]) {
          ans.append(str2.charAt(--j));
        } else {
          ans.append(str1.charAt(--i));
          --j;
        }
      }
    }
    return ans.reverse().toString();
  }
}

class Solution {
public:
  string shortestCommonSupersequence(string str1, string str2) {
    int m = str1.size(), n = str2.size();
    vector<vector<int>> f(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (str1[i - 1] == str2[j - 1])
          f[i][j] = f[i - 1][j - 1] + 1;
        else
          f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
    int i = m, j = n;
    string ans;
    while (i || j) {
      if (i == 0)
        ans += str2[--j];
      else if (j == 0)
        ans += str1[--i];
      else {
        if (f[i][j] == f[i - 1][j])
          ans += str1[--i];
        else if (f[i][j] == f[i][j - 1])
          ans += str2[--j];
        else
          ans += str1[--i], --j;
      }
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

func shortestCommonSupersequence(str1 string, str2 string) string {
  m, n := len(str1), len(str2)
  f := make([][]int, m+1)
  for i := range f {
    f[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      if str1[i-1] == str2[j-1] {
        f[i][j] = f[i-1][j-1] + 1
      } else {
        f[i][j] = max(f[i-1][j], f[i][j-1])
      }
    }
  }
  ans := []byte{}
  i, j := m, n
  for i > 0 || j > 0 {
    if i == 0 {
      j--
      ans = append(ans, str2[j])
    } else if j == 0 {
      i--
      ans = append(ans, str1[i])
    } else {
      if f[i][j] == f[i-1][j] {
        i--
        ans = append(ans, str1[i])
      } else if f[i][j] == f[i][j-1] {
        j--
        ans = append(ans, str2[j])
      } else {
        i, j = i-1, j-1
        ans = append(ans, str1[i])
      }
    }
  }
  for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  return string(ans)
}

function shortestCommonSupersequence(str1: string, str2: string): string {
  const m = str1.length;
  const n = str2.length;
  const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (str1[i - 1] == str2[j - 1]) {
        f[i][j] = f[i - 1][j - 1] + 1;
      } else {
        f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  let ans: string[] = [];
  let i = m;
  let j = n;
  while (i > 0 || j > 0) {
    if (i === 0) {
      ans.push(str2[--j]);
    } else if (j === 0) {
      ans.push(str1[--i]);
    } else {
      if (f[i][j] === f[i - 1][j]) {
        ans.push(str1[--i]);
      } else if (f[i][j] === f[i][j - 1]) {
        ans.push(str2[--j]);
      } else {
        ans.push(str1[--i]);
        --j;
      }
    }
  }
  return ans.reverse().join('');
}