🌱 Keegan's Digital Garden

1309. Decrypt String from Alphabet to Integer Mapping

2 min read

Leetcode

📝 Problem Details

💭What Were My Initial Thoughts?

- we need a way of determining whether a character is mapped to a single or double digit
- mind first went to using stoi and then int to char but that seemed inefficient

🤔What Did I Struggle With?

- remembering the code for string matching 
- I was too hung up on my initial proposed solution that I could not think of another *logical* approach

💡 Explanation of Solution

- by starting from the back of the string, we can accurately determine the length of the number since it will start with a # rather than end with it

⌛ Complexity Analysis

Time Compelxity: O(n)
- we only require a single pass-through of the input string, where N is equal to the number of characters in the string

Space Complexity: O(n)
- an additional results vector containing a worst case of n elements

💻 Implementation of Solution

class Solution {
public:
    string freqAlphabets(string s) {
        string res = "";
 
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '#') { // Handle two-digit numbers
                // Construct the number backward
                int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0'); 
 
                res.push_back('a' - 1 + num);
                i -= 2; // Skip the two digits and the '#'
            } else { // Handle single-digit numbers
                res.push_back('a' - 1 + (s[i] - '0'));
            }
        }
 
        reverse(res.begin(), res.end()); // Reverse the result string
        return res;
    }
};

Graph View