[LeetCode] 1048. Longest String Chain

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".

word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2word_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 }

LeetCode 题目总结

原文地址:https://www.cnblogs.com/cnoodle/p/14800312.html