SMS Dictionary || Codechef Solution

 

SMS Dictionary

In the pre-smartphone era, most mobile phones with numeric keypads had a private dictionary of words to allow users to type messages quicker. On a typical phone of this type, each number key is assigned a subset of the alphabet {a,b,…,z}: 2 is assigned the subset {a,b,c}, 3 is assigned {d,e,f}, 4 is assigned {g,h,i}, 5 is assigned {j,k,l}, 6 is assigned {m,n,o}, 7 is assigned {p,q,r,s}, 8 is assigned {t,u,v} and 9 is assigned {w,x,y,z}. When the user types a sequence of numbers, this sequence is mapped to all possible words that can be constructed from the key assignment. For instance, if the user types 66, this could correspond to any one of the letter sequences "mm", "mn", "mo", "nm", "nn", "no", "om", "on" or "oo". These letter sequences are looked up in the dictionary stored in the phone and all matches are reported. For instance, if the phone's dictionary contains only "on" and "no" from this set of sequences, the user will be offered a choice of "on" or "no" to insert in the message. Similarly, the input 4663 might be interpreted as either "good" or "home". An input sequence may have a unique interpretation---for example, the only word in the dictionary matching the input 28 may be "at". Other sequences may not match any word in the dictionary—for instance, 99999. Your task is the following. Given the typical assignment from number keys to letters of the alphabet given above and given a dictionary of words, report the input sequence that matches the largest number of words in the dictionary. For example, if the dictionary consists of the words {at,on,good,no} then the answer is 66, because 66 matches both "on" and "no" while no other input matches more than one word in the dictionary. On the other hand, with the dictionary {at,on,good,no,home,gone}, the answer is 4663, because 4663 matches three.

words, "good", "home" and "gone" in the dictionary.

• Solution:

1. Python3.6 

try:

    n = int(input())

    words = [input() for _ in range(n)]

    words_nums = {}

    for i in words:

    seq = ""

    for j in i:

    if j in ['a','b','c']:

    seq+='2'

    elif j in ['d','e','f']:

    seq+='3'

    elif j in ['g','h','i']:

    seq+='4'

    elif j in ['j','k','l']:

    seq+='5'

    elif j in ['m','n','o']:

    seq+='6'

    elif j in ['p','q','r','s']:

    seq+='7'

    elif j in ['t','u','v']:

    seq+='8'

    elif j in ['w','x','y','z']:

    seq+='9'

    if int(seq) in words_nums:

    words_nums[int(seq)]+=1

    else:

    words_nums[int(seq)] = 1

    print(max(words_nums, key = words_nums.get))

except:

    pass

1. C++

#include<stdio.h>

#define ll long long

#include <string.h>

int map[] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};

int freq[100000005] = {};

int main() {

    ll n, cnt = 0, res;

    char s[15];

    scanf("%lld", &n);

    for (ll i = 0; i < n; i++) {

        scanf("%s", s);

    

        ll val = 0;

        for (ll j = 0; j < strlen(s); j++) {

            val *= 10;

            val += map[s[j] - 'a'];

        }

        freq[val]++;

        if(freq[val] > cnt) {

            cnt = freq[val];

            res = val;

        }

    }

    printf("%lld", res);

    return 0;

}

🙏THANKS FOR VISIT🙏