↓Skip to main content
  1. Posts/

LeetCode-1092 最短公共超序列

·1 min·
Table of Contents

LeetCode-1092 最短公共超序列 #

Solution 1 #

如果 $s[-1] = t[-1]$ , 那么所求超序列的最后一位一定是 $s[-1]$ ; 否则有两种构造方式, 选择更短的那一种, 这个过程可以递归地进行. 重点在于通过反推构造来节省内存空间. make_ans 的思路值得认真思考.

代码如下:

class Solution:
    def shortestCommonSupersequence(self, s: str, t: str) -> str:
        @cache 
        def f(i, j):
            if i == 0:
                return j
            if j == 0:
                return i
            if s[i - 1] == t[j - 1]:
                return f(i - 1, j - 1) + 1
            return min(f(i - 1, j), f(i, j - 1)) + 1
        
        def make_ans(i, j):
            if i == 0:
                return t[:j]
            if j == 0:
                return s[:i]
            if s[i - 1] == t[j - 1]:
                return make_ans(i - 1, j - 1) + s[i - 1]
            if f(i, j) == f(i - 1, j) + 1:
                return make_ans(i - 1, j) + s[i - 1]
            return make_ans(i, j - 1) + t[j - 1]
        
        return make_ans(len(s), len(t))