171. Excel Sheet Column Number
Some tips about ASCII and mathematics
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 columnTitle
s 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)
, whereN = 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
) minus64
.The parentheses around
(c - 64)
is needed. Otherwise the value ofcolumnTitle = "FXSHRXW"
makes26*column + c
exceed the limit ofint
before it substracts64
.
References
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.