Decrypt String from Alphabet to Integer Mapping Leetcode Solution


Difficulty Level Easy
Frequently asked in Quip Salesforce
String

Problem Statement

In this problem, we are given a string containing digits (0-9) and ‘#’. We have to convert this string to a string of lowercase english letters by using the following mapping.

Decrypt String from Alphabet to Integer Mapping Leetcode Solution

Example

s = "10#11#12"
"jkab"

Explanation:

“10#” -> “j” , “11#” -> “k” , “1” -> “a” , “2” -> “b”.

s = "1326#"
"acz"

Explanation:

“1” -> “a” , “3” -> “c” , “26#” -> “z”.

Approach

We can see that we just have to concern about ‘#’. When we traverse the given string from left to right using counter (let i), then, for each index i (0<=i<=n-3), we just have to check if the character at next to next index from i i.e. character at index i+2 is ‘#’.

For each i (0 to n-3), if character at index i+2 is ‘#’ then combine this index i with i+1 and form a character using these two digits.
e.g. “12#” ,  if we traverse the string from left to right, We see that when i=0 then character at index i+2 is ‘#’. Thus combine digits present at indexes i and i+1 i.e. combine digits 1 and 2, make them “12”. Now convert 12 to its character mapping i.e. “l” and append it into stringbuilder sb.
To convert string “12” to character ‘l’, we have created a convert function, which takes a number in string format and convert it to corresponding character.
And if the character at index i+2 is not ‘#’ then we should not combine character at index i with character at index i+1.

e.g. “123” ,  if we see from index i=0, index i+2 i.e. character at 2 is not ‘#’, thus we will just append character conversion of “1” in our answer.

For character at index n-2 and n-1, we can say that if char at n-1 would be already ‘#’, then we would be out of the loop after index n-3, else both characters at n-2 and n-1 must be mapped separately.

Implementation

C++ Program for Decrypt String from Alphabet to Integer Mapping Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

char convert(string str){
    stringstream ss(str);
    int num;
    ss>>num;
    return num+96;
}

string freqAlphabets(string s) {
        stringstream ss;
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s[i+2]=='#'){
                ch=(char)convert(s.substr(i, 2) );
                i+=2;
            }else{
                ch=(char)convert(s.substr(i,1));
            }
            i++;
            ss<<ch;
        }
        while(i<s.length()){
            char ch=(char)convert(s.substr(i,1));
            ss<<ch;
            i++;
        }
        
        return ss.str();
    }

int main()
{
    cout << freqAlphabets("1326#") ;
}
acz

Java Program for Decrypt String from Alphabet to Integer Mapping Leetcode Solution

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static String freqAlphabets(String s) {
        StringBuilder sb=new StringBuilder();
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s.charAt(i+2)=='#'){
                ch=(char)convert(s.substring(i,i+2));
                i+=2;
            }else{
                ch=(char)convert(s.substring(i,i+1));
            }
            i++;
            sb.append(ch);
        }
        while(i<s.length()){
            char ch=(char)convert(s.substring(i,i+1));
            sb.append(ch);
            i++;
        }
        
        return sb.toString();
    }
    
    
    public static int convert(String str){
        int num=Integer.parseInt(str);
        return num+96;
    }

    public static void main(String args[])
    {
        System.out.println(freqAlphabets("10#11#12"));
    }
}
jkab

Complexity Analysis for Decrypt String from Alphabet to Integer Mapping Leetcode Solution

Time Complexity

O(n): Because we are traversing our input string linearly from left to right thus O(n) time will be taken.

Space Complexity 

O(n): We have used a string builder in case of java and string stream in cpp. In worst case then length would be same as input string length. Thus, space complexity too is O(n).