longest-string-chain

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of <code>words</code> where each word consists of lowercase English letters.

<code>wordA</code> is a predecessor of <code>wordB</code> if and only if we can insert exactly one letter anywhere in <code>wordA</code> without changing the order of the other characters to make it equal to <code>wordB</code>.

<ul>
	<li>For example, <code>&quot;abc&quot;</code> is a predecessor of <code>&quot;abac&quot;</code>, while <code>&quot;cba&quot;</code> is not a predecessor of <code>&quot;bcad&quot;</code>.</li>
</ul>

A word chain is a sequence of words <code>[word1, word2, ..., wordk]</code> with <code>k &gt;= 1</code>, where <code>word1</code> is a predecessor of <code>word2</code>, <code>word2</code> is a predecessor of <code>word3</code>, and so on. A single word is trivially a word chain with <code>k == 1</code>.

Return the length of the longest possible word chain with words chosen from the given list of <code>words</code>.

&nbsp;
Example 1:

<pre>
Input: words = [&quot;a&quot;,&quot;b&quot;,&quot;ba&quot;,&quot;bca&quot;,&quot;bda&quot;,&quot;bdca&quot;]
Output: 4
Explanation: One of the longest word chains is [&quot;a&quot;,&quot;ba&quot;,&quot;bda&quot;,&quot;bdca&quot;].
</pre>

Example 2:

<pre>
Input: words = [&quot;xbc&quot;,&quot;pcxbcf&quot;,&quot;xb&quot;,&quot;cxbc&quot;,&quot;pcxbc&quot;]
Output: 5
Explanation: All the words can be put in a word chain [&quot;xb&quot;, &quot;xbc&quot;, &quot;cxbc&quot;, &quot;pcxbc&quot;, &quot;pcxbcf&quot;].
</pre>

Example 3:

<pre>
Input: words = [&quot;abcd&quot;,&quot;dbqca&quot;]
Output: 1
Explanation: The trivial word chain [&quot;abcd&quot;] is one of the longest word chains.
[&quot;abcd&quot;,&quot;dbqca&quot;] is not a valid word chain because the ordering of the letters is changed.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 16</code></li>
	<li><code>words[i]</code> only consists of lowercase English letters.</li>
</ul>

longestStrChain

Longest String Chain

Array

Hash Table

Two Pointers

String

Dynamic Programming

Sorting

给出一个单词数组&nbsp;<code>words</code>&nbsp;，其中每个单词都由小写英文字母组成。

如果我们可以&nbsp;不改变其他字符的顺序&nbsp;，在 <code>wordA</code>&nbsp;的任何地方添加 恰好一个 字母使其变成&nbsp;<code>wordB</code>&nbsp;，那么我们认为&nbsp;<code>wordA</code>&nbsp;是&nbsp;<code>wordB</code>&nbsp;的 前身 。

<ul>
	<li>例如，<code>"abc"</code>&nbsp;是&nbsp;<code>"abac"</code>&nbsp;的 前身&nbsp;，而&nbsp;<code>"cba"</code>&nbsp;不是&nbsp;<code>"bcad"</code>&nbsp;的 前身</li>
</ul>

词链是单词&nbsp;<code>[word_1, word_2, ..., word_k]</code>&nbsp;组成的序列，<code>k &gt;= 1</code>，其中&nbsp;<code>word1</code>&nbsp;是&nbsp;<code>word2</code>&nbsp;的前身，<code>word2</code>&nbsp;是&nbsp;<code>word3</code>&nbsp;的前身，依此类推。一个单词通常是 <code>k == 1</code> 的 单词链&nbsp;。

从给定单词列表 <code>words</code> 中选择单词组成词链，返回 词链的&nbsp;最长可能长度 。 
&nbsp;

示例 1：

<pre>
输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]
</pre>

示例 2:

<pre>
输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
</pre>

示例&nbsp;3:

<pre>
输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 16</code></li>
	<li><code>words[i]</code>&nbsp;仅由小写英文字母组成。</li>
</ul>