Leetcode 1309. Decrypt String from Alphabet to Integer Mapping

Problem Explanation:

In this problem, we are given a string made up of numbers and '#' characters, and we are required to convert this string into an English language string using a specific mapping. The map is described as such:

  • Characters from 'a' to 'i' map to the numbers '1' to '9' respectively.
  • Characters from 'j' to 'z' map to the strings '10#' to '26#' respectively.

Our task is to decode the given string using this mapping, and return the corresponding English string.

Let's walk through an example. Suppose we are given a string '1326#'. Start decoding from left to right: first digit is '1', mapping with 'a'; then digit '3', mapping with 'c'. The last part '26#' in one unit mapping with 'z'. Therefore, the decoded string would be 'acz'.

Solution Approach:

One simple approach to solve this problem is by iterating over the string in reverse. Why reverse? Because each '#', along with the two preceding numbers, forms one unit that represents a single character. Looking from the right helps us easily determine whether we have such a unit (i.e., '10#' to '26#') or a single-digit number.

While iterating from the right in our code, we check whether the current character is a '#'. If it is, we take the preceding two numbers, convert them to a single character according to the mapping, and then move 3 steps backwards. If the current character is not '#', we take this single digit, convert it to a character, and move one step backwards.

Finally, we will get the decoded English string after going through all characters in the input string.

Python Solution:

1
2python
3class Solution:
4    def freqAlphabets(self, s: str) -> str:
5        i, ans = len(s) - 1, ''
6        while i >= 0:
7            if s[i] == '#':
8                ans += chr(int(s[i-2:i]) + 96)
9                i -= 3
10            else:
11                ans += chr(int(s[i]) + 96)
12                i -= 1
13        return ans[::-1]

Java Solution:

1
2java
3class Solution {
4    public String freqAlphabets(String s) {
5        StringBuilder ans = new StringBuilder();
6        int i = s.length() - 1;
7        while(i >= 0) {
8            if(s.charAt(i) == '#') {
9                ans.append((char)(Integer.parseInt(s.substring(i-2, i)) + 96));
10                i -= 3;
11            } else {
12                ans.append((char)(Integer.parseInt(s.substring(i, i+1)) + 96));
13                i -= 1;
14            }
15        }
16        return ans.reverse().toString();
17    }
18}

JavaScript Solution:

1
2javascript
3var Solution = function() {};
4Solution.prototype.freqAlphabets = function(s) {
5    let ans = '';
6    for(let i = s.length - 1; i >= 0;) {
7        if(s[i] === '#') {
8            ans = String.fromCharCode(parseInt(s.substring(i-2, i)) + 96) + ans;
9            i -= 3;
10        } else {
11            ans = String.fromCharCode(parseInt(s[i]) + 96) + ans;
12            i -= 1;
13        }
14    }
15    return ans;
16};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    string freqAlphabets(string s) {
6        string ans;
7        for(int i=s.size()-1;i>=0;) {
8            if(s[i] == '#') {
9                ans += char(stoi(s.substr(i-2, 2)) + 96);
10                i -= 3;
11            } else {
12                ans += char(s[i] - '0' + 96);
13                i--;
14            }
15        }
16        reverse(ans.begin(), ans.end());
17        return ans;
18    }
19};

C# Solution:

1
2csharp
3public class Solution {
4    public string FreqAlphabets(string s) {
5        StringBuilder ans = new StringBuilder();
6        int i = s.Length - 1;
7        while(i >= 0) {
8            if(s[i] == '#') {
9                ans.Insert(0, (char)(int.Parse(s.Substring(i-2, 2)) + 96));
10                i -= 3;
11            } else {
12                ans.Insert(0, (char)(int.Parse(s.Substring(i, 1)) + 96));
13                i -= 1;
14            }
15        }
16        return ans.ToString();
17    }
18}

In all of these solutions, we're using the ASCII values of English characters to convert the numbers from the input string to English characters directly. So '+96' is used because ASCII of 'a' is 97 and we're subtracting '1' because the mapping of 'a' is '1'.Ruby Solution:

1
2ruby
3class Solution
4    def initialize
5    end
6
7    def freq_alphabets(s)
8        ans = []
9        i = s.length - 1
10        while i >= 0 do
11            if s[i] == '#'
12                ans.unshift ((s[i-2..i-1].to_i + 96).chr)
13                i -= 3
14            else
15                ans.unshift ((s[i].to_i + 96).chr)
16                i -= 1
17            end
18        end
19        ans.join
20    end
21end

Haskell Solution:

1
2Haskell
3import Data.Char
4
5freqAlphabets :: String -> String
6freqAlphabets [] = []
7freqAlphabets ('#':xs) = chr (96 + read (take 2 xs)) : freqAlphabets (drop 2 xs)
8freqAlphabets (x:xs) = chr (96 + digitToInt x) : freqAlphabets xs

GoLang Solution:

1
2Go
3import "strconv"
4
5func freqAlphabets(s string) string {
6	ans := make([]rune, 0)
7	i := len(s) - 1
8	for i >= 0 {
9		if s[i] == '#' {
10            num, _ := strconv.Atoi(s[i-2 : i])
11			ans = append([]rune{rune(num + 96)}, ans...)
12			i -= 3
13		} else {
14            num, _ := strconv.Atoi(s[i : i+1])
15			ans = append([]rune{rune(num + 96)}, ans...)
16			i--
17		}
18	}
19	return string(ans)
20}

In the Ruby, Haskell, and GoLang solutions, we are also using the ASCII mapping of English characters to decode the string. We iterate backwards through the string like in other solutions. If the current character is a '#', we convert the preceding two characters to a number, add 96 to it to get the ASCII value, and then convert it to a character. If the current character is not a '#', we convert it to a number, add 96 to get the ASCII value, and then convert it to a character. We continue this until we've processed all the characters in the string, resulting in our decoded string.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫