Leetcode Daily - August 10, 2020

Excel Sheet Column Number

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

Constraints:

• 1 <= s.length <= 7
• s consists only of uppercase English letters.
• s is between "A" and "FXSHRXW".

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Treat the string as a base 26 number

(Submission - Accepted)

After trying out some examples by hand, I realized that this column naming system is basically a base 26 number. The notable difference is that instead of having a zero digit, we start at 1 with A and end at 26 with Z. Then, 27 resets to AA, which is:

 27 = 1*26 + 1*1 
 27 = A*(26^1) + A*(26^0)

Similarly, ZY, which is 701, can be broken down as:

 701 = 26*26 + 25*1 
 701 = Z*(26^1) + Y*(26^0)

Even without the zero digit, we can be fairly confident in our conversion system. The numbers start counting at 26 to the zeroth power, just like how other number bases start at the zeroth power.

With this we can write our Javascript code, which starts at the right side of the string and starts iterating the powers of 26. I used a dictionary to convert the individual letters to numbers.

Submitted Code:

var titleToNumber = function(s) {
    // s is a string, but basically converts to a number in base 26 
    // also instead of zero we have 26 
    const dict = {
        A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8, I: 9, J: 10, K: 11, L: 12, M: 13, N: 14,
        O: 15, P: 16, Q: 17, R: 18, S: 19, T: 20, U: 21, V: 22, W: 23, X: 24, Y: 25, Z: 26
    }
    let number = 0;
    let power = 0;
    for (let i = s.length-1; i >= 0; i--) {
        number += Math.pow(26, power)*dict[s[i]];
        power ++;
    }
    return number;
};

Attempt 1A - Still Treating the string as a base 26 number

(Submission - Accepted)

I just wanted to try writing this but reading the string's digits from left to right instead of right to left. Instead of adding the correct power of 26, this iterative method takes the previous number and multiplies all of it by 26 (because it's all numbers from left to right so far), and then adds the specific digit.

Submitted Code:

var titleToNumber = function(s) {
    // s is a string, but basically converts to a number in base 26 
    // also instead of zero we have 26 
    const dict = {
        A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8, I: 9, J: 10, K: 11, L: 12, M: 13, N: 14,
        O: 15, P: 16, Q: 17, R: 18, S: 19, T: 20, U: 21, V: 22, W: 23, X: 24, Y: 25, Z: 26
    }
    let number = 0;

    for (let i = 0; i < s.length; i++) {
        number = number*26 + dict[s[i]];
    }
    return number;
};

Discussion and Conclusions

There is not much I want to say about this question. Once the naming/numbering system is understood, the conversion can be done as a numerical base 26 conversion, with the added step of parsing the string. Even though I'm sure there are ways to optimize the code, I believe this is sufficient understanding of the problem.

The time complexity is O(n) for n equal to the length of string s, but the length of s is constrained to be less than or equal to 7.