22 ноября, 2020 
rius 
In this post I will tell how to find all matches for a number like 400-9663626. A match in this case is a 7 letter word composed using specific rules. For this telephone number we’ll get 400-WOODMAN. I will use binary search. In the picture three letters are missing: O Q Z.
Here is a sample from the dictionary file:
Abandon Abating Abdomen Abetted Abetter ... Zipping Zombies Zoology Zooming Zoominh |
Note. Zoominh is a made up word. I needed it to test the case when there are more than 1 word with the same characteristic number.
In the program I take into account that the first letter is upper case and the rest are lower case.
Here are the rules of translation in the normal direction:
static Map<character, string=""> map = new HashMap<>(); static { map.put('0', ""); map.put('1', ""); map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); } |
(WordPress spoils the java code)
Here are the rules for reversed order:
static Map<character, integer=""> reversedMap = new HashMap<>(); static { reversedMap.put('a', 2); reversedMap.put('b', 2); reversedMap.put('c', 2); reversedMap.put('d', 3); reversedMap.put('e', 3); reversedMap.put('f', 3); reversedMap.put('g', 4); reversedMap.put('h', 4); reversedMap.put('i', 4); reversedMap.put('j', 5); reversedMap.put('k', 5); reversedMap.put('l', 5); reversedMap.put('m', 6); reversedMap.put('n', 6); reversedMap.put('o', 6); reversedMap.put('p', 7); reversedMap.put('q', 7); reversedMap.put('r', 7); reversedMap.put('s', 7); reversedMap.put('t', 8); reversedMap.put('u', 8); reversedMap.put('v', 8); reversedMap.put('w', 9); reversedMap.put('x', 9); reversedMap.put('y', 9); reversedMap.put('z', 9); } |
The dictionary file is here: P4WORDS.TXT
All the lines files are read into the List of NumberWrappers. In this class I store array of chars as well as the characteristic number. Note that the class implements Comparable interface and defines method int compareTo(NumberWrapper o), which compares characteristic numbers.
The list is sorted this way: Collections.sort(words);
And after that I can input a 7-digit number and find it’s position in the sorted list:
int position = Collections.binarySearch(words, new NumberWrapper(sampleNumber));
If the evaluated position is negative, then there is no match.
If it equals to zero or a positive number, then there is at least one match. To find all of them, I use this loop:
// Moving back from the found position till we find the same number - needed // for the case when there are several words with the same number if (position >= 0) { System.out.println("Found:"); while (words.get(position).number == sampleNumber) { System.out.println(words.get(position)); position--; } } else { System.out.println("nothing found"); } |
So, for the number 9666464 I can find 2 matches:
NumberWrapper{chars=[Z, o, o, m, i, n, h], number=9666464}
NumberWrapper{chars=[Z, o, o, m, i, n, g], number=9666464} |
Full java source is available here: https://github.com/dk2k/java_experiments/tree/master/p4_words_binary_search
Posted in 
Tags: