Leetcode 2135: Count Words Obtained After Adding a Letter
In this Leetcode problem, we are asked to transform some words from an array of words to target words. Any word from the initial array can be used to be transformed in a target word using a specific transformation rule.
You are given two 0-indexed arrays of strings
targetWords. Each string consists of lowercase English letters only.
For each string in
targetWords, check if it is possible to choose a string from
startWordsand perform a conversion operation on it to be equal to that from
The conversion operation is described in the following two steps:
Append any lowercase letter that is not present in the string to its end.
For example, if the string is
"abc", the letters
'y'can be added to it, but not
'd'is added, the resulting string will be
Rearrange the letters of the new string in any arbitrary order.
"abcd"can be rearranged to
"cbda", and so on. Note that it can also be rearranged to
Return the number of strings in
targetWordsthat can be obtained by performing the operations on any string of
Note that you will only be verifying if the string in
targetWordscan be obtained from a string in
startWordsby performing the operations. The strings in
startWordsdo not actually change during this process.
We are trying to be the most effective possible in solving this problem.
The first observation we can do is that the order of letter doesn’t matter at all, as we can rearrange it anyway we want. There are way to exploit it by for instance storing the words as a map of character to integer, with the number of occurrence for each character, or as an array of ints as is done in the next figure:
In the end, I decided to reorder the letters alphabetically in the string. For instance: “example” would become “aeelmpx”. This is a way to normalize the string, and the same set of letters will always show up in the same order.
The second thing that improves efficiency is that instead of doing the first step “appending”, that is adding a letter, we can remove a letter from target words. Target words have a length that is less than 26 characters, so it is more efficient to remove a letter.