171. Excel Sheet Column Number

Problem statement

Given a string columnTitle that represents the column title as appears 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: columnTitle = "A"
Output: 1

Example 2

Input: columnTitle = "AB"
Output: 28

Example 3

Input: columnTitle = "ZY"
Output: 701

Constraints

1 <= columnTitle.length <= 7.
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Solution: Finding The Pattern

Let us write down some other columnTitle strings and its value.

"A"   =  1
"Z"   =  26
"AA"  =  27
"AZ"  =  52
"ZZ"  =  702
"AAA" =  703

Then try to find the pattern

"A"   =  1    =  1
"Z"   =  26   =  26
"AA"  =  27   =  26 + 1
"AZ"  =  52   =  26 + 26
"ZZ"  =  702  =  26*26 + 26
"AAA" =  703  =  26*26 + 26 + 1

If you map 'A' = 1, ..., 'Z' = 26, the values can be rewritten as

"A"   =  1    =  'A'
"Z"   =  26   =  'Z'
"AA"  =  27   =  26*'A' + 'A'
"AZ"  =  52   =  26*'A' + 'Z'
"ZZ"  =  702  =  26*'Z' + 'Z'
"AAA" =  703  =  26*26*'A' + 26*'A' + 'A'

In general the formula for a string columnTitle = abcd is

abcd = 26^3*a + 26^2*b + 26*c + d,

where a, b, c, d are some uppercase English letters A, ..., Z.

Longer columnTitles will have bigger leading exponents of 26.

Code

#include <iostream>
using namespace std;
int titleToNumber(string columnTitle) {
    int column = 0; 
    for (char c : columnTitle) {
        // The ASCII value of 'A' is 65.
        column = 26*column + (c - 64); 
    }
    return column;
}
int main() {
    cout << titleToNumber("A") << endl;
    cout << titleToNumber("AB") << endl;
    cout << titleToNumber("ZY") << endl;
}

Output:
1
28
701

Complexity

Runtime: O(N), where N = columnTitle.length.
Extra space: O(1).

Implementation notes

There are many ways to compute the series
```
 26^3*a + 26^2*b + 26*c + d.
```
If you write it as
```
 26*(26*(26*(0 + a) + b) + c) + d,
```
you get the loop in the code above.
To map 'A' = 1, ..., 'Z' = 26, you can use their ASCII values ('A' = 65, ..., 'Z' = 90) minus 64.
The parentheses around (c - 64) is needed. Otherwise the value of columnTitle = "FXSHRXW" makes 26*column + c exceed the limit of int before it substracts 64.

References

https://leetcode.com/problems/excel-sheet-column-number/

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.

171. Excel Sheet Column Number

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Finding The Pattern

Code

Complexity

Implementation notes

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Finding The Pattern

Code

Complexity

Implementation notes

References