171. Excel Sheet Column Number

Description

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

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @return {number}
 */

//idea: we treat the string as numbers in base 26
let titleToNumber = function(s) {
    let str = s;
    let result = 0;
    let val = 0;
    let power = 0;
    while(str !== ""){
        //the Unicode value for A is 65 so we subtract 64 from s's value
        val = str.charAt(str.length - 1).charCodeAt(0) - 64;
        val *= Math.pow(26, power);
        result += val;
        
        power++;
        str = str.substring(0, str.length - 1);
    }
    
    return result;
    
};

Analysis

This was a cute little problem. We're basically working with base 26, so a string like ABC would be A*26^2 + B*26^1 + C*26^0. The algorithm is exactly the same as converting binary to decimal only we work with powers of 26 instead of 2.

I liked this problem a lot even if it was easy. I never thought about why Excel's columns are named the way they are before. I mean I always made the connection that you had columns A-Z and then AA, AB, etc. for 27, 28, etc. It's just that this really made me realize it's a lot easier typing, say, CATS9 instead of having to type something like 53943,9. Though I'm not sure what kind of spreadsheet would have 50,000+ columns. Apparently Microsoft has asked this question in some of their coding interviews. I find that really nice for reason.

So anyway, since we iterate over each letter of the string exactly once, the running time for this algorithm is just O(n) where n is the length of the string.