Given a set of words, find the longest chain of words that can be made out of those words with the following rules:
-
Each word in the chain is one letter longer than the previous word.
-
Each word in the chain differs from the previous word only by its last letter.
Write test case's. Also, mention the Time and Space complexity for the same.
Constraint Examples:
den -> dent-> dents is valid (meets all constraints)
den -> dew is not valid (same length: 3 characters)
den -> cent is not valid (differs by 1’st char [‘d’ != ‘c’]) Example:
Input: {ben, bent, dew, dents, dent, bet, den}
Output: 3 ({den, dent, dents})
Comments (9)