Soundex is a phonetic algorithm, meaning that it indexes words by their pronunciation (in English). The algorithm transforms an input string of letters into a code of the form Cddd, where C is an uppercase letter and each d character represents a digit between 0 and 6, inclusive.
The variant of Soundex we will be using works as follows:
- Remember the first letter of the input string.
- Remove all H and W characters.
- Replace each letter in the word with its phonetic code, given in the following table:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 0 1 2 - 0 2 2 4 5 5 0 1 2 6 2 3 0 1 - 2 0 2
- Compress runs consisting of the same digit, leaving only one occurrence.
- Remove all occurrences of the digit zero.
- Truncate the result or pad it with zeros from the right so that the resulting code is exactly four characters long (for example, the string 123456 would be truncated to 1234, while the string 43 would be padded with zeros to form 4300).
- Replace the first digit by the letter remembered in the first step.
For example, let's run through the algorithm with the word SOMEWHERE:
- We remember the letter S as we will need to restore it later.
- Removing the H and W characters yields SOMEERE.
- Replacing letters with their phonetic codes results in 2050060.
- Compressing groups of consecutive codes gives 205060.
- Removing all zeros, we get 256.
- Padding the result with a single zero gives 2560.
- Restoring the first letter gives the final S560.
Find the number of distinct words of length length, consisting only of letters of the English alphabet, for which the above algorithm yields the given Soundex code soundex. |