mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
53 lines
2.5 KiB
HTML
53 lines
2.5 KiB
HTML
<p>You are given an array of strings <code>words</code>. Find all <strong>shortest common supersequences (SCS)</strong> of <code><font face="monospace">words</font></code> that are not <span data-keyword="permutation-string">permutations</span> of each other.</p>
|
|
|
|
<p>A <strong>shortest common supersequence</strong> is a string of <strong>minimum</strong> length that contains each string in <code>words</code> as a <span data-keyword="subsequence-string-nonempty">subsequence</span>.</p>
|
|
|
|
<p>Return a 2D array of integers <code>freqs</code> that represent all the SCSs. Each <code>freqs[i]</code> is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">words = ["ab","ba"]</span></p>
|
|
|
|
<p><strong>Output: </strong>[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]</p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The two SCSs are <code>"aba"</code> and <code>"bab"</code>. The output is the letter frequencies for each one.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">words = ["aa","ac"]</span></p>
|
|
|
|
<p><strong>Output: </strong>[[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]</p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The two SCSs are <code>"aac"</code> and <code>"aca"</code>. Since they are permutations of each other, keep only <code>"aac"</code>.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">words = </span>["aa","bb","cc"]</p>
|
|
|
|
<p><strong>Output: </strong>[[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]</p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p><code>"aabbcc"</code> and all its permutations are SCSs.</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= words.length <= 256</code></li>
|
|
<li><code>words[i].length == 2</code></li>
|
|
<li>All strings in <code>words</code> will altogether be composed of no more than 16 unique lowercase letters.</li>
|
|
<li>All strings in <code>words</code> are unique.</li>
|
|
</ul>
|