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”.
Did you find this article valuable?
Support LeetSolve by becoming a sponsor. Any amount is appreciated!