<p>Given two strings <code>str1</code> and <code>str2</code>, return <em>the shortest string that has both </em><code>str1</code><em> and </em><code>str2</code><em> as <strong>subsequences</strong></em>. If there are multiple valid strings, return <strong>any</strong> of them.</p>

<p>A string <code>s</code> is a <strong>subsequence</strong> of string <code>t</code> if deleting some number of characters from <code>t</code> (possibly <code>0</code>) results in the string <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;abac&quot;, str2 = &quot;cab&quot;
<strong>Output:</strong> &quot;cabac&quot;
<strong>Explanation:</strong> 
str1 = &quot;abac&quot; is a subsequence of &quot;cabac&quot; because we can delete the first &quot;c&quot;.
str2 = &quot;cab&quot; is a subsequence of &quot;cabac&quot; because we can delete the last &quot;ac&quot;.
The answer provided is the shortest such string that satisfies these properties.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;aaaaaaaa&quot;, str2 = &quot;aaaaaaaa&quot;
<strong>Output:</strong> &quot;aaaaaaaa&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>
	<li><code>str1</code> and <code>str2</code> consist of lowercase English letters.</li>
</ul>

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        w1, w2 = len(str1), len(str2)
        dp = collections.defaultdict(lambda:float("inf"))
        for i in range(w1+1):
            dp[i,0] = i
        for i in range( w2+1):
            dp[0,i] = i
        for i in range(1, w1+1):
            for j in range(1, w2+1):
                if str1[i-1] == str2[j-1]:
                    dp[i,j] = dp[i-1,j-1] + 1
                else:
                    dp[i,j] = min(dp[i-1,j], dp[i, j-1]) + 1
        
        result = []
        t = (w1, w2)
        while True:
            i,j = t
            if i == 0 and j==0:
                break
            c1 = str1[i-1] if i>0 else ""
            c2 = str2[j-1] if j>0 else ""

            if c1 == c2:
                result.append(c1)
                t = (i-1, j-1)
            elif dp[i-1, j] < dp[i, j-1]:
                result.append(c1)
                t = (i-1, j)
            else:
                result.append(c2)
                t = (i, j-1)

        result.reverse()
        return "".join(result)
206183