mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-12 02:41:42 +08:00
88 lines
3.9 KiB
HTML
88 lines
3.9 KiB
HTML
<p>You are given two strings, <code>str1</code> and <code>str2</code>, of lengths <code>n</code> and <code>m</code>, respectively.</p>
|
|
|
|
<p>A string <code>word</code> of length <code>n + m - 1</code> is defined to be <strong>generated</strong> by <code>str1</code> and <code>str2</code> if it satisfies the following conditions for <strong>each</strong> index <code>0 <= i <= n - 1</code>:</p>
|
|
|
|
<ul>
|
|
<li>If <code>str1[i] == 'T'</code>, the <strong><span data-keyword="substring-nonempty">substring</span></strong> of <code>word</code> with size <code>m</code> starting at index <code>i</code> is <strong>equal</strong> to <code>str2</code>, i.e., <code>word[i..(i + m - 1)] == str2</code>.</li>
|
|
<li>If <code>str1[i] == 'F'</code>, the <strong><span data-keyword="substring-nonempty">substring</span></strong> of <code>word</code> with size <code>m</code> starting at index <code>i</code> is <strong>not equal</strong> to <code>str2</code>, i.e., <code>word[i..(i + m - 1)] != str2</code>.</li>
|
|
</ul>
|
|
|
|
<p>Return the <strong><span data-keyword="lexicographically-smaller-string">lexicographically smallest</span></strong> possible string that can be <strong>generated</strong> by <code>str1</code> and <code>str2</code>. If no string can be generated, return an empty string <code>""</code>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">str1 = "TFTF", str2 = "ab"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">"ababa"</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<h4>The table below represents the string <code>"ababa"</code></h4>
|
|
|
|
<table>
|
|
<tbody>
|
|
<tr>
|
|
<th style="border: 1px solid black;">Index</th>
|
|
<th style="border: 1px solid black;">T/F</th>
|
|
<th style="border: 1px solid black;">Substring of length <code>m</code></th>
|
|
</tr>
|
|
<tr>
|
|
<td style="border: 1px solid black;">0</td>
|
|
<td style="border: 1px solid black;"><code>'T'</code></td>
|
|
<td style="border: 1px solid black;">"ab"</td>
|
|
</tr>
|
|
<tr>
|
|
<td style="border: 1px solid black;">1</td>
|
|
<td style="border: 1px solid black;"><code>'F'</code></td>
|
|
<td style="border: 1px solid black;">"ba"</td>
|
|
</tr>
|
|
<tr>
|
|
<td style="border: 1px solid black;">2</td>
|
|
<td style="border: 1px solid black;"><code>'T'</code></td>
|
|
<td style="border: 1px solid black;">"ab"</td>
|
|
</tr>
|
|
<tr>
|
|
<td style="border: 1px solid black;">3</td>
|
|
<td style="border: 1px solid black;"><code>'F'</code></td>
|
|
<td style="border: 1px solid black;">"ba"</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
|
|
<p>The strings <code>"ababa"</code> and <code>"ababb"</code> can be generated by <code>str1</code> and <code>str2</code>.</p>
|
|
|
|
<p>Return <code>"ababa"</code> since it is the lexicographically smaller string.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">str1 = "TFTF", str2 = "abc"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">""</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>No string that satisfies the conditions can be generated.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">str1 = "F", str2 = "d"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">"a"</span></p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= n == str1.length <= 10<sup>4</sup></code></li>
|
|
<li><code>1 <= m == str2.length <= 500</code></li>
|
|
<li><code>str1</code> consists only of <code>'T'</code> or <code>'F'</code>.</li>
|
|
<li><code>str2</code> consists only of lowercase English characters.</li>
|
|
</ul>
|