longest-common-prefix-between-adjacent-strings-after-removals

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an array of strings <code>words</code>. For each index <code>i</code> in the range <code>[0, words.length - 1]</code>, perform the following steps:

<ul>
	<li>Remove the element at index <code>i</code> from the <code>words</code> array.</li>
	<li>Compute the length of the longest common prefix among all adjacent pairs in the modified array.</li>
</ul>

Return an array <code>answer</code>, where <code>answer[i]</code> is the length of the longest common prefix between the adjacent pairs after removing the element at index <code>i</code>. If no adjacent pairs remain or if none share a common prefix, then <code>answer[i]</code> should be 0.

&nbsp;
Example 1:

<div class="example-block">
Input: words = [&quot;jump&quot;,&quot;run&quot;,&quot;run&quot;,&quot;jump&quot;,&quot;run&quot;]

Output: [3,0,0,3,3]

Explanation:

<ul>
	<li>Removing index 0:
	<ul>
		<li><code>words</code> becomes <code>[&quot;run&quot;, &quot;run&quot;, &quot;jump&quot;, &quot;run&quot;]</code></li>
		<li>Longest adjacent pair is <code>[&quot;run&quot;, &quot;run&quot;]</code> having a common prefix <code>&quot;run&quot;</code> (length 3)</li>
	</ul>
	</li>
	<li>Removing index 1:
	<ul>
		<li><code>words</code> becomes <code>[&quot;jump&quot;, &quot;run&quot;, &quot;jump&quot;, &quot;run&quot;]</code></li>
		<li>No adjacent pairs share a common prefix (length 0)</li>
	</ul>
	</li>
	<li>Removing index 2:
	<ul>
		<li><code>words</code> becomes <code>[&quot;jump&quot;, &quot;run&quot;, &quot;jump&quot;, &quot;run&quot;]</code></li>
		<li>No adjacent pairs share a common prefix (length 0)</li>
	</ul>
	</li>
	<li>Removing index 3:
	<ul>
		<li><code>words</code> becomes <code>[&quot;jump&quot;, &quot;run&quot;, &quot;run&quot;, &quot;run&quot;]</code></li>
		<li>Longest adjacent pair is <code>[&quot;run&quot;, &quot;run&quot;]</code> having a common prefix <code>&quot;run&quot;</code> (length 3)</li>
	</ul>
	</li>
	<li>Removing index 4:
	<ul>
		<li>words becomes <code>[&quot;jump&quot;, &quot;run&quot;, &quot;run&quot;, &quot;jump&quot;]</code></li>
		<li>Longest adjacent pair is <code>[&quot;run&quot;, &quot;run&quot;]</code> having a common prefix <code>&quot;run&quot;</code> (length 3)</li>
	</ul>
	</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: words = [&quot;dog&quot;,&quot;racer&quot;,&quot;car&quot;]

Output: [0,0,0]

Explanation:

<ul>
	<li>Removing any index results in an answer of 0.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 105</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 104</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>105</code>.</li>
</ul>

第 456 场周赛

weekly-contest-456

longestCommonPrefix

高级工程师

Longest Common Prefix Between Adjacent Strings After Removals

Array

String

给你一个字符串数组 <code>words</code>，对于范围 <code>[0, words.length - 1]</code> 内的每个下标&nbsp;<code>i</code>，执行以下步骤：

<ul>
	<li>从 <code>words</code> 数组中移除下标&nbsp;<code>i</code> 处的元素。</li>
	<li>计算修改后的数组中所有&nbsp;相邻对&nbsp;之间的&nbsp;最长公共前缀&nbsp;的长度。</li>
</ul>

返回一个数组 <code>answer</code>，其中 <code>answer[i]</code> 是移除下标&nbsp;<code>i</code> 后，相邻对之间最长公共前缀的长度。如果 不存在&nbsp;相邻对，或者&nbsp;不存在&nbsp;公共前缀，则 <code>answer[i]</code> 应为 0。

字符串的前缀是从字符串的开头开始延伸到任意位置的子字符串。

&nbsp;

示例 1：

<div class="example-block">
输入： words = ["jump","run","run","jump","run"]

输出： [3,0,0,3,3]

解释：

<ul>
	<li>移除下标&nbsp;0：
	<ul>
		<li><code>words</code> 变为 <code>["run", "run", "jump", "run"]</code></li>
		<li>最长的相邻对是 <code>["run", "run"]</code>，其公共前缀为 <code>"run"</code>（长度为 3）</li>
	</ul>
	</li>
	<li>移除下标&nbsp;1：
	<ul>
		<li><code>words</code> 变为 <code>["jump", "run", "jump", "run"]</code></li>
		<li>没有相邻对有公共前缀（长度为 0）</li>
	</ul>
	</li>
	<li>移除下标&nbsp;2：
	<ul>
		<li><code>words</code> 变为 <code>["jump", "run", "jump", "run"]</code></li>
		<li>没有相邻对有公共前缀（长度为 0）</li>
	</ul>
	</li>
	<li>移除下标&nbsp;3：
	<ul>
		<li><code>words</code> 变为 <code>["jump", "run", "run", "run"]</code></li>
		<li>最长的相邻对是 <code>["run", "run"]</code>，其公共前缀为 <code>"run"</code>（长度为 3）</li>
	</ul>
	</li>
	<li>移除下标&nbsp;4：
	<ul>
		<li><code>words</code> 变为 <code>["jump", "run", "run", "jump"]</code></li>
		<li>最长的相邻对是 <code>["run", "run"]</code>，其公共前缀为 <code>"run"</code>（长度为 3）</li>
	</ul>
	</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： words = ["dog","racer","car"]

输出： [0,0,0]

解释：

<ul>
	<li>移除任意下标都会导致答案为 0。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= words.length &lt;= 105</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 104</code></li>
	<li><code>words[i]</code> 仅由小写英文字母组成。</li>
	<li><code>words[i]</code> 的长度总和不超过 <code>105</code>。</li>
</ul>