The Confused Mobile Keypad
All submissions for this problem are available.
ByteLandSoft has launched a new mobile phone which has got a T9 keyboard. They have introduced a new feature which lets you type without pressing the same key multiple times. That is, if you want to enter a letter, you have to press the key it corresponds to just once. For example, if you want to enter ‘q’, you have to press 7 only once ('p', 'q', 'r' and 's' correspond to 7, remember?). With the help of a list of commonly used words (i.e. a dictionary), the add-on tries to predict the word the user wants to type. For instance, if the series of key-presses be 466453, the user must be trying to type “google”.
But there’s a catch here. If there is more than one word in the dictionary which correspond to the same series of key-presses, the add-on gets confused. That is, two words in the dictionary are said to be confusing if they correspond to the same series of key-presses.
Given a list of lower-case words, find the number of confusing pairs of words in the list.
· Line 1: A single integer N.
· Lines 2 to N+1: Each of these lines consist of a single word...containing only lowercase letters. They are not necessarily valid English words.
Print a single integer, the number of confusing pairs.
The largest test file consists of all English words (not necessarily in alphabetical order).
The two pairs are:
· ”abc” and “bab” both correspond to 222.
· “dbd” and “eaf” both correspond to 323.
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.