mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
70 lines
3.5 KiB
HTML
70 lines
3.5 KiB
HTML
<p>You are given an array of strings <code>words</code> and an integer <code>k</code>.</p>
|
|
|
|
<p>For each index <code>i</code> in the range <code>[0, words.length - 1]</code>, find the <strong>length</strong> of the <strong>longest common <span data-keyword="string-prefix">prefix</span></strong> among any <code>k</code> strings (selected at <strong>distinct indices</strong>) from the remaining array after removing the <code>i<sup>th</sup></code> element.</p>
|
|
|
|
<p>Return an array <code>answer</code>, where <code>answer[i]</code> is the answer for <code>i<sup>th</sup></code> element. If removing the <code>i<sup>th</sup></code> element leaves the array with fewer than <code>k</code> strings, <code>answer[i]</code> is 0.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">words = ["jump","run","run","jump","run"], k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[3,4,4,3,4]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>Removing index 0 (<code>"jump"</code>):
|
|
|
|
<ul>
|
|
<li><code>words</code> becomes: <code>["run", "run", "jump", "run"]</code>. <code>"run"</code> occurs 3 times. Choosing any two gives the longest common prefix <code>"run"</code> (length 3).</li>
|
|
</ul>
|
|
</li>
|
|
<li>Removing index 1 (<code>"run"</code>):
|
|
<ul>
|
|
<li><code>words</code> becomes: <code>["jump", "run", "jump", "run"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
|
|
</ul>
|
|
</li>
|
|
<li>Removing index 2 (<code>"run"</code>):
|
|
<ul>
|
|
<li><code>words</code> becomes: <code>["jump", "run", "jump", "run"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
|
|
</ul>
|
|
</li>
|
|
<li>Removing index 3 (<code>"jump"</code>):
|
|
<ul>
|
|
<li><code>words</code> becomes: <code>["jump", "run", "run", "run"]</code>. <code>"run"</code> occurs 3 times. Choosing any two gives the longest common prefix <code>"run"</code> (length 3).</li>
|
|
</ul>
|
|
</li>
|
|
<li>Removing index 4 ("run"):
|
|
<ul>
|
|
<li><code>words</code> becomes: <code>["jump", "run", "run", "jump"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">words = ["dog","racer","car"], k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[0,0,0]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>Removing any index results in an answer of 0.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= k <= words.length <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= words[i].length <= 10<sup>4</sup></code></li>
|
|
<li><code>words[i]</code> consists of lowercase English letters.</li>
|
|
<li>The sum of <code>words[i].length</code> is smaller than or equal <code>10<sup>5</sup></code>.</li>
|
|
</ul>
|