Convert Sentence
You are given a sentence in the form of a string ‘S’. You have to convert ‘S’ into its equivalent mobile numeric keypad sequence, i.e. print the sequence in such a way that if it is typed on the given keypad, the output should be the string ‘S’. A keypad for the reference is shown below.

Note:

1. There will be only lower case letters. 2. There will not be any special characters or capital letters in the input string. 3. There will be no spaces in the string.

Input Format:

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains one integer N, denoting the length of the string ‘S’. The second line of each test case contains the input string ‘S’.

Output Format:

The only line of output of each test case consists of an output string, denoting the pattern which is required to print ‘S’. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Convert Sentence

You are given a sentence in the form of a string ‘S’. You have to convert ‘S’ into its equivalent mobile numeric keypad sequence, i.e. print the sequence in such a way that if it is typed on the given keypad, the output should be the string ‘S’. A keypad for the reference is shown below.

Note:

1. There will be only lower case letters.
2. There will not be any special characters or capital letters in the input string.
3. There will be no spaces in the string.

Input Format:

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains one integer N, denoting the length of the string ‘S’.
The second line of each test case contains the input string ‘S’.

Output Format:

The only line of output of each test case consists of an output string, denoting the pattern which is required to print ‘S’. 
The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 3000

Where 'T' is the number of test cases and ' N' is the length of the sentence 'S'.

Accepted Answer

Approach :

1) For each character, we can store what should be typed on the keypad. We can store this information in a string array named ‘freq’.

2) The size of freq[] will be 26 and index 0 will store the pattern for ‘a’, index 1 will store the pattern for ‘b’ and so on..Index 25 will store the pattern for ‘z’.

3) The pattern for ‘a’ is 2, for ‘z’ is 9999, for ‘n’ is 66 and so on.

4) After storing the pattern in the array, we will take an output string and while traversing the string and we will get the pattern corresponding to the current character from the freq array and add it to our output string.

TC : O(N), where N=size of the string
SC : O(26)

Accepted Answer

Implementation

The simplest possible approach is to write how many times we have to press a particular key to get a character.
For each character, we can store what should be typed on the keypad. We can store this information in a string array named ‘freq’.
The size of freq[] will be 26 and index 0 will store the pattern for ‘a’, index 1 will store the pattern for ‘b’ and so on.. Index 25 will store the pattern for ‘z’.
The pattern for ‘a’ is 2, for ‘z’ is 9999, for ‘n’ is 66 and so on.
After storing the pattern in the array, we will take an output string and while traversing the string and we will get the pattern corresponding to the current character from the freq array and add it to our output string.

Space Complexity: O(1)Explanation:

O(26).

Since we are storing the frequency pattern for each character and there can only be 26 unique characters in the given string.

Time Complexity: O(n)Explanation:

O(N), where N is the size of the string

Since we are traversing the string only once. Also, filling the ‘freq’ array takes O(26) time. Thus, the final time complexity is O(26 + N) = O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space complexity: O(26)

    Where N is the size of the given string.
*/

public class Solution {
	public static String convertSentence(String s, int n) {

		// Creating a frequency array.
		String freq[] = { "2", "22", "222", "3", "33", "333", "4", "44", "444", "5", "55", "555", "6", "66", "666", "7",
				"77", "777", "7777", "8", "88", "888", "9", "99", "999", "9999" };

		StringBuilder ans = new StringBuilder();
		for (int i = 0; i < n; i++) {
			// Finding the position of the character in the freq array.

			int pos = (s.charAt(i) - 'a');
			ans.append(freq[pos]);
		}

		return ans.toString();
	}
}

Python (3.5)

def convertSentence(s: str, n: int):

    

    # Store the sequence for letters

    freq = ["2", "22", "222", 

       "3", "33", "333", 

       "4", "44", "444", 

       "5", "55", "555", 

       "6", "66", "666", 

       "7", "77", "777", "7777", 

       "8", "88", "888", 

       "9", "99", "999", "9999" ]

    

    ans = ""

    for i in range(n):

        pos = ord(s[i]) - ord('a')

        ans += freq[pos]

        

    return ans

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space complexity: O(26)

    Where N is the size of the given string.
*/

string convertSentence(string s, int n) {

	// Creating a frequency array.
	string freq[] = {"2", "22", "222",
	                 "3", "33", "333",
	                 "4", "44", "444",
	                 "5", "55", "555",
	                 "6", "66", "666",
	                 "7", "77", "777", "7777",
	                 "8", "88", "888",
	                 "9", "99", "999", "9999"
	                };

	string ans = "";
	for (int i = 0; i < n; i++) {
		// Finding the position of the character in the freq array.
		int pos = s[i] - 'a';
		ans += freq[pos];
	}

	return ans;
}

You are given a sentence in the form of a string ‘S’. You have to convert ‘S’ into its equivalent mobile numeric keypad sequence, i.e. print the sequence in such a way that if it is typed on the given keypad, the output should be the string ‘S’. A keypad for the reference is shown below.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top UST Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in UST Software Engineer