Description: You are provided a dictionary of words in a form of a list of size n.You have to find Longest String Chain Length as per following explanation:
From the dictionary, you pick up a word and in each step, you remove a single letter from it and check whether the remaining word is still in the dictionary. If the remaining word is present in the dictionary you increase the chain length by one. You perform the same operations until you are left with the last remaining word present in the dictionary.
Mind it, you have to remove every possible character in the string and check the remaining word for chain length.
Input :
a
b
ba
bca
bda
bdca
Output: 4
Input :
a
b
ba
bca
bda
bdca
Output: 4
Explanation:
You are provided with the following words in the dictionary :
“a”, “b”, “ba”, “bca”, “bda”, “bdca”
As “a” and “b” are single-character words, If we remove the only character in them then we would be left with empty Strings of length 0. So we cannot remove any characters from them. So the length for both of these string chains is 1(their original length).
You are provided with the following words in the dictionary :
“a”, “b”, “ba”, “bca”, “bda”, “bdca”
As “a” and “b” are single-character words, If we remove the only character in them then we would be left with empty Strings of length 0. So we cannot remove any characters from them. So the length for both of these string chains is 1(their original length).
The word “ba” can make two different string chains of length 2
“ba” --> “a” and “ba” --> “b”
This means now the longest string chain is 2.
The word “bca” can make two different string chains of length 3
(“bca” --> “ba” --> “a” and “bca” --> “ba” --> “b”)
This means now the longest string chain is 3.
This means now the longest string chain is 2.
The word “bca” can make two different string chains of length 3
(“bca” --> “ba” --> “a” and “bca” --> “ba” --> “b”)
This means now the longest string chain is 3.
The word “bda” can create two different string chains of length 3
“bda” --> “ba” --> “a” and “bda” --> “ba” --> “b”
This means now the longest string chain is now 3.
“bda” --> “ba” --> “a” and “bda” --> “ba” --> “b”
This means now the longest string chain is now 3.
The word “bdca” can make four different string chains of length 4
“bdca” --> “bda” --> “ba” --> “a” ,
“bdca” --> “bda” --> “ba” --> “b”,
“bdca” --> “bca” --> “ba” --> “a”,
“bdca” --> “bca” --> “ba"" --> ”b”
This means now the longest string chain is now 4.
“bdca” --> “bda” --> “ba” --> “a” ,
“bdca” --> “bda” --> “ba” --> “b”,
“bdca” --> “bca” --> “ba” --> “a”,
“bdca” --> “bca” --> “ba"" --> ”b”
This means now the longest string chain is now 4.
Implementation: The implementation has been done with a recursive approach using memoization (Dynamic Programming).But still, it could be done with Iterative approach.
If the constraints are too restricted we should prefer tabulation approach or any other iterative approach.
If the constraints are too restricted we should prefer tabulation approach or any other iterative approach.