Given a list of words, each word consists of English lowercase letters.
Let's say word1
is a predecessor of word2
if and only if we can add exactly one letter anywhere in word1
to make it equal to word2
. For example, "abc"
is a predecessor of "abac"
.
A word chain is a sequence of words [word_1, word_2, ..., word_k]
with k >= 1
, where word_1
is a predecessor of word_2
, word_2
is a predecessor of word_3
, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words
.
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: One of the longest word chain is "a","ba","bda","bdca".
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]
only consists of English lowercase letters.
最长字符串链。
给出一个单词列表,其中每个单词都由小写英文字母组成。
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1 是 word2 的前身。例如,"abc" 是 "abac" 的前身。
词链是单词 [word_1, word_2, ..., word_k] 组成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此类推。
从给定单词列表 words 中选择单词组成词链,返回词链的最长可能长度。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-string-chain
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题我给出一个hashmap的思路。这里我们一开始创建一个HashMap<word, length of the chain starts with this word>,存的是每个单词和以当前这个单词为结尾的最长的链的长度是多少。此时我们将 input 数组按照单词长度排序,这样单词长度短的在前。
对于每个单词而言,如果他不能跟其他任何单词形成链表,那么以这个单词为结尾的链表的长度起码就是 1,这是一开始我需要把每个单词存入hashmap放的默认值。接着我们开始遍历 input 中的每个单词 w,对于当前这个单词 w 而言,我们需要按char逐个尝试删除字符,这样我们会形成一个新的,更短的单词 next。我们去hashmap看一下这个更短的单词 next 是否存在,如果存在,同时需要看一下 next 在hashmap中是否存在一个比以 w 结尾的更长的链表,如果有,则更新 w 在 hashmap 的 value。
时间O(nlogn) - need to sort the input array
空间O(n) - hashmap
Java实现
1 class Solution { 2 public int longestStrChain(String[] words) { 3 // <each word, longest chain starts with this word> 4 HashMap<String, Integer> map = new HashMap<>(); 5 6 int res = 0; 7 Arrays.sort(words, (a, b) -> a.length() - b.length()); 8 for (String w : words) { 9 map.put(w, 1); 10 for (int i = 0; i < w.length(); i++) { 11 StringBuilder sb = new StringBuilder(w); 12 String next = sb.deleteCharAt(i).toString(); 13 if (map.containsKey(next) && map.get(next) + 1 > map.get(w)) { 14 map.put(w, map.get(next) + 1); 15 } 16 } 17 res = Math.max(res, map.get(w)); 18 } 19 return res; 20 } 21 }