Skip to content

1309. Decrypt String from Alphabet to Integer Mapping

Description

You are given a string s formed by digits and '#'. We want to map s to English lowercase characters as follows:

  • Characters ('a' to 'i') are represented by ('1' to '9') respectively.
  • Characters ('j' to 'z') are represented by ('10#' to '26#') respectively.

Return the string formed after mapping.

The test cases are generated so that a unique mapping will always exist.

 

Example 1:

Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

Example 2:

Input: s = "1326#"
Output: "acz"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of digits and the '#' letter.
  • s will be a valid string such that mapping is always possible.

Solutions

Solution 1: Simulation

Thinking

The mapping has two widths: a single digit for \(1\)–\(9\), and three characters with # for \(10\)–\(26\). Reading every token as one digit splits 10# incorrectly. At each index we look two steps ahead: a # consumes two digits, otherwise one digit, and the cursor advances by \(3\) or \(1\).

We can directly simulate the process.

Traverse the string \(s\). For the current index \(i\), if \(i + 2 < n\) and \(s[i + 2]\) is #, then convert the substring formed by \(s[i]\) and \(s[i + 1]\) to an integer, add the ASCII value of a minus 1, convert it to a character, add it to the result array, and increment \(i\) by 3. Otherwise, convert \(s[i]\) to an integer, add the ASCII value of a minus 1, convert it to a character, add it to the result array, and increment \(i\) by 1.

Finally, convert the result array to a string and return it.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def freqAlphabets(self, s: str) -> str:
        ans = []
        i, n = 0, len(s)
        while i < n:
            if i + 2 < n and s[i + 2] == "#":
                ans.append(chr(int(s[i : i + 2]) + ord("a") - 1))
                i += 3
            else:
                ans.append(chr(int(s[i]) + ord("a") - 1))
                i += 1
        return "".join(ans)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    string freqAlphabets(string s) {
        string ans = "";
        int i = 0, n = s.size();
        while (i < n) {
            if (i + 2 < n && s[i + 2] == '#') {
                ans += char(stoi(s.substr(i, 2)) + 'a' - 1);
                i += 3;
            } else {
                ans += char(s[i] - '0' + 'a' - 1);
                i += 1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func freqAlphabets(s string) string {
    var ans []byte
    for i, n := 0, len(s); i < n; {
        if i+2 < n && s[i+2] == '#' {
            num := (int(s[i])-'0')*10 + int(s[i+1]) - '0'
            ans = append(ans, byte(num+int('a')-1))
            i += 3
        } else {
            num := int(s[i]) - '0'
            ans = append(ans, byte(num+int('a')-1))
            i += 1
        }
    }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function freqAlphabets(s: string): string {
    const ans: string[] = [];
    for (let i = 0, n = s.length; i < n;) {
        if (i + 2 < n && s[i + 2] === '#') {
            ans.push(String.fromCharCode(96 + +s.slice(i, i + 2)));
            i += 3;
        } else {
            ans.push(String.fromCharCode(96 + +s[i]));
            i++;
        }
    }
    return ans.join('');
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn freq_alphabets(s: String) -> String {
        let s = s.as_bytes();
        let mut ans = String::new();
        let mut i = 0;
        let n = s.len();
        while i < n {
            if i + 2 < n && s[i + 2] == b'#' {
                let num = (s[i] - b'0') * 10 + (s[i + 1] - b'0');
                ans.push((96 + num) as char);
                i += 3;
            } else {
                let num = s[i] - b'0';
                ans.push((96 + num) as char);
                i += 1;
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
char* freqAlphabets(char* s) {
    int n = strlen(s);
    int i = 0;
    int j = 0;
    char* ans = malloc(sizeof(s) * n);
    while (i < n) {
        int t;
        if (i + 2 < n && s[i + 2] == '#') {
            t = (s[i] - '0') * 10 + s[i + 1];
            i += 3;
        } else {
            t = s[i];
            i += 1;
        }
        ans[j++] = 'a' + t - '1';
    }
    ans[j] = '\0';
    return ans;
}

Comments