Problem Link - Word Hopping
Problem Statement -
In this problem we are concerned with words constructed using the lowercase letters of the English alphabet - that is, a,b,c,...,z. These words need not necessarily be meaningful: any sequence of letters forms a word. For example, abbca is a word.
We say that we can “hop” from the word w1 to the word w2 if they are “sufficiently close”. We define w2 to be sufficiently close to w1 if one of the following holds: w2 is obtained from w1 by deleting one letter.w2 is obtained from w1 by replacing one of the letters in w1 by some letter that appears to its right in w1 and which is also to its right in alphabetical order.
For example, we can hop from abbca to abca by deleting the second (or third letter). We can hop from aabca to abbca by replacing the a in the second position by the letter b that appears to the right of the a in aabca and which is also to its right in alphabetical order. On the other hand we cannot hop from abbca to aabca since we would need to replace the b in the second position by a, but a is to the left of b in alphabetical order.
You will be given a collection of words W. Your task is to find the length of the longest sequence w1,w2,… of distinct words from W such that we may hop from w1 to w2, w2 to w3 and so on. We call this the hopping number for this set.
Approach
The solution starts by sorting the words in decreasing order of length. If two words have the same length, they are sorted alphabetically. This ensures that longer words are processed first, making it easier to check possible hops.
For each word, the program calculates the longest hopping sequence using dynamic programming. It checks subsequent words to see if a valid hop exists, either by deleting a character or replacing one with a valid character based on the rules.
Two helper functions handle this:
-
“RightHop” checks if a word can be formed by replacing a character with another valid one.
-
“DeleteHop” checks if a word can be formed by deleting a character.
The maximum hopping sequence length is updated for each word, and the largest value in the DP table gives the hopping number.
Time Complexity
The time complexity is O(n^2 \times m), where n is the number of words and m is the average length of a word, because each pair of words is compared and checked for hops.
Space Complexity
The space complexity is O(n), as the dynamic programming array stores the maximum hopping sequence length for each word.