Decrypt String from Alphabet to Integer Mapping Leetcode Solution

Difficulty Level Easy
Frequently asked in Quip Salesforce
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 2250

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).

Translate »