LeetCode 1048. Longest String Chain Solution
You are given an array of words
where each word consists of
lowercase English letters.
wordA
{" "}
is a predecessor of{" "}
wordB
{" "}
if and only if we can insert exactly one letter anywhere in{" "}
wordA
{" "}
without changing the order of the other characters to make
it equal to{" "}
wordB
.
-
For example,
"abc"
is a predecessor of{" "}"abac"
, while"cba"
is not a predecessor of{" "}"bcad"
.
A word chain
is a sequence of words{" "}
[word1, word2, ..., wordk]
{" "}
with k >= 1
, where{" "}
word1
{" "}
is a predecessor of{" "}
word2
,{" "}
word2
{" "}
is a predecessor of{" "}
word3
, and so on. A single word is trivially a word chain with{" "}
k == 1
.
Return{" "}
the length of the{" "}
longest possible word chain with words chosen from the
given list of{" "}
words
.
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"]{"\n"} Output: 4{"\n"} Explanation: One of the longest word chains is ["a"," ba","bda","bdca"].{"\n"}
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]{"\n"} Output: 5{"\n"} Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].{"\n"}
Example 3:
Input: words = ["abcd","dbqca"]{"\n"} Output: 1{"\n"} Explanation: The trivial word chain ["abcd"] is one of the longest word chains.{"\n"}["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.{"\n"}
Constraints:
-
1 <= words.length <= 1000
-
1 <= words[i].length <= 16
-
words[i]
only consists of lowercase English letters.
Problem Link: https://leetcode.com/problems/longest-string-chain/
Solution
Naive Solutions
We could go through all possible chains and check if each works, or we could use a recursive function that adds one character every time, but these solutions are too slow.
Dynamic Programming Solution
Let's build a chain from the shortest string to the longest string. Say we currently have the chain . We see that it doesn't matter what any of the words before are, only that there are of them. This suggests a dynamic programming solution, where the length of the longest chain that ends with the string .
First sort by increasing length. An outer loop will loop . For each , we have an inner loop to check every word before it to see if it can be a predecessor. We'll call this index . If so, we update to because we can extend the chain ending in by appending .
For example, when , , and , we find that removing from yields .
Time complexity
Let and .
Sorting takes .
Our nested loops take and call isPredecessor()
that runs in , so this part takes .
The total time complexity of this algorithm is therefore .
Space complexity
The array consumes memory.
Solutions below
C++ Solution
1class Solution {
2 public:
3 bool isPredecessor(string &previous_word, string ¤t_word) {
4 if (previous_word.size() + 1 == current_word.size()) {
5 for (int k = 0; k < current_word.size(); k++) {
6 if (previous_word == current_word.substr(0, k) + current_word.substr(k + 1))
7 return true;
8 }
9 }
10 return false;
11 }
12 int longestStrChain(vector<string> &words) {
13 // sort words by length
14 sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
15 int n = words.size();
16 vector<int> dp(n, 1);
17 for (int current_word_index = 0; current_word_index < n; current_word_index++) {
18 for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
19 if (isPredecessor(words[j], words[current_word_index])) {
20 dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1);
21 }
22 }
23 }
24 return *max_element(dp.begin(), dp.end());
25 }
26};
Java Solution
1class Solution {
2 public static boolean isPredecessor(String previous_word, String current_word) {
3 if (previous_word.length() + 1 == current_word.length()) {
4 for (int k = 0; k < current_word.length(); k++) {
5 if (previous_word.equals(current_word.substring(0, k) + current_word.substring(k+1)))
6 return true;
7 }
8 }
9 return false;
10 }
11 public int longestStrChain(String[] words) {
12 // sort words by length
13 Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
14 int n = words.length;
15
16 // add padding to words to avoid index out of bounds errors
17 for (int i = 0; i < n; i++) {
18 words[i] = "#" + words[i];
19 }
20
21 int ans = 1;
22 int[] dp = new int[n];
23 Arrays.fill(dp, 1);
24 for (int current_word_index = 0; current_word_index < n; current_word_index++) {
25 for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
26 if (isPredecessor(words[previous_word_index], words[current_word_index])) {
27 dp[current_word_index] = Math.max(dp[current_word_index], dp[previous_word_index] + 1);
28 ans = Math.max(ans, dp[current_word_index]);
29 }
30
31 }
32 }
33 return ans;
34 }
35}
Python Solution
1class Solution: 2 def isPredecessor(self, previous_word, current_word): 3 if len(previous_word) + 1 == len(current_word): 4 for k in range(len(current_word)): 5 if previous_word == current_word[0:k] + current_word[k+1:]: 6 return True 7 return False 8 9 def longestStrChain(self, words: List[str]) -> int: 10 words.sort(key=len) 11 n = len(words) 12 dp = [1 for _ in range(n)] 13 for current_word_index in range(n): 14 for previous_word_index in range(current_word_index): 15 if self.isPredecessor(words[previous_word_index], words[current_word_index]): 16 dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1) 17 return max(dp)
JavaScript Solution
1var isPredecessor = function (previous_word, current_word) { 2 if (previous_word.length + 1 == current_word.length) { 3 for (let k = 0; k < current_word.length; k++) { 4 if ( 5 previous_word === 6 current_word.slice(0, k) + current_word.slice(k + 1) 7 ) 8 return true; 9 } 10 } 11 return false; 12}; 13 14/** 15 * @param {string[]} words 16 * @return {number} 17 */ 18var longestStrChain = function (words) { 19 // sort words by length 20 words.sort((a, b) => a.length - b.length); 21 n = words.length; 22 dp = new Array(n).fill(1); 23 24 for ( 25 let current_word_index = 0; 26 current_word_index < n; 27 current_word_index++ 28 ) { 29 for ( 30 let previous_word_index = 0; 31 previous_word_index < current_word_index; 32 previous_word_index++ 33 ) { 34 if ( 35 isPredecessor(words[previous_word_index], words[current_word_index]) 36 ) { 37 dp[current_word_index] = Math.max( 38 dp[current_word_index], 39 dp[previous_word_index] + 1 40 ); 41 } 42 } 43 } 44 return Math.max(...dp); 45};
Dynamic Programming Solution (requires HashMap)
In our last solution, checking all previous words for predecessors was slow.
Observe that each word can only have predecessors, so we can generate them all (in ) and check the best value we can get from them.
Let the length of the longest chain that ends with the string . will be a hashmap to allow for retrieval by key.
As we did before, sort by increasing length. Loop through the current string . Then for each index , let be with its th character removed. Set to . Our answer is the max of all entries in .
Time complexity
Let and .
Sorting takes .
For every string (there are of them), create each of its predecessors in and check for their value in in . This comes together to .
The total time complexity is therefore .
Space complexity
The hashmap consumes memory.
Bonus:
We can perform counting sort in , giving a total time complexity of .
Solutions below
C++ Solution
1class Solution {
2public:
3 int longestStrChain(vector<string> &words) {
4 // sort words by length
5 sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
6 int n = words.size(), ans = 1;
7 unordered_map<string, int> dp;
8 for (auto ¤t_word: words) {
9 for (int j = 0; j < current_word.size(); j++) {
10 string previous_word = current_word.substr(0, j) + current_word.substr(j + 1);
11 dp[current_word] = max(dp[current_word], dp[previous_word] + 1);
12 }
13 ans = max(ans, dp[current_word]);
14 }
15 return ans;
16 }
17};
Java Solution
1class Solution {
2 public int longestStrChain(String[] words) {
3 // sort words by length
4 Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
5 int n = words.length;
6 // add padding to words so that we don't have to do s.substring(0, -1).
7 // which would throw an index out of bounds error
8 for (int i = 0; i < n; i++) {
9 words[i] = "#" + words[i];
10 }
11 TreeMap<String, Integer> dp = new TreeMap<>();
12 int ans = 1;
13 for (String current_word: words) {
14 dp.put(current_word, 1);
15 for (int j = 0; j < current_word.length(); j++) {
16 String previous_word = current_word.substring(0, j) + current_word.substring(j + 1);
17 dp.put(current_word, Math.max(dp.get(current_word), dp.getOrDefault(previous_word, 0) + 1));
18 }
19 ans = Math.max(ans, dp.get(current_word));
20 }
21 return ans;
22 }
23}
Python Solution
1class Solution: 2 def longestStrChain(self, words: List[str]) -> int: 3 # sort words by length 4 words.sort(key=len) 5 n = len(words) 6 ans = 0 7 dp = defaultdict(lambda: 0) 8 for current_word in words: 9 for j in range(len(current_word)): 10 previous_word = current_word[0:j] + current_word[j+1:] 11 dp[current_word] = max(dp[current_word], dp[previous_word] + 1) 12 ans = max(ans, dp[current_word]) 13 return ans
JavaScript Solution
1/** 2 * @param {string[]} words 3 * @return {number} 4 */ 5var longestStrChain = function (words) { 6 words.sort((a, b) => a.length - b.length); 7 n = words.length; 8 dp = new Map(); 9 ans = 0; 10 for (current_word of words) { 11 dp[current_word] = 1; 12 for (let j = 0; j < s.length; j++) { 13 previous_word = current_word.slice(0, j) + current_word.slice(j + 1); 14 // We need (dp[previous_word] || 0) to get 0 if dp does not contain previous_word, otherwise we'd get Nan, 15 // which is larger than any integer 16 dp[current_word] = Math.max( 17 dp[current_word], 18 (dp[previous_word] || 0) + 1 19 ); 20 } 21 ans = Math.max(ans, dp[current_word]); 22 } 23 return ans; 24};