LeetCode 171: Excel Sheet Column Number

Problem Restatement

We are given an Excel column title:

columnTitle

We need to return its corresponding column number.

Excel columns are labeled like this:

This problem is the reverse of LeetCode 168.

The input contains only uppercase English letters. The constraints guarantee the answer fits in a 32-bit integer. (leetcode.com)

Input and Output

Example function shape:

def titleToNumber(columnTitle: str) -> int:
    ...

Examples

Example 1:

columnTitle = "A"

Output:

1

Example 2:

columnTitle = "AB"

Compute:

A = 1
B = 2

So:

1 * 26 + 2 = 28

Return:

28

Example 3:

columnTitle = "ZY"

Compute:

Z = 26
Y = 25

So:

26 * 26 + 25 = 701

Return:

701

First Thought: This Is Like Base 26

This looks similar to converting a number written in base 26.

For example:

"AB"

behaves like:

1 * 26 + 2

But there is one important difference.

Normal base 26 digits are:

0 through 25

Excel digits are:

1 through 26

Still, the accumulation process is almost identical to normal positional notation.

Key Insight

Process the string from left to right.

Suppose we already computed the value of the prefix.

When we read a new character, shift the old value left by one base-26 position:

result *= 26

Then add the new digit value.

Character conversion:

"A" -> 1
"B" -> 2
...
"Z" -> 26

We can compute this using ASCII codes:

ord(ch) - ord("A") + 1

Why the Formula Works

Suppose we process:

"AB"

Start:

result = 0

Read "A":

result = 0 * 26 + 1 = 1

Read "B":

result = 1 * 26 + 2 = 28

This matches the Excel column number.

The multiplication by 26 shifts previous digits one position to the left, exactly like decimal numbers use multiplication by 10.

Algorithm

Initialize:

result = 0

For each character ch in columnTitle:

1. Convert the character into its numeric value.
2. Multiply result by 26.
3. Add the digit value.

Return result.

Walkthrough

Use:

columnTitle = "ZY"

Start:

result = 0

Read "Z":

value = 26
result = 0 * 26 + 26 = 26

Read "Y":

value = 25
result = 26 * 26 + 25 = 701

Return:

701

Correctness

The algorithm processes the column title from left to right.

Suppose after processing the first k characters, result equals the correct numeric value of that prefix.

When the next character is read, multiplying by 26 shifts the previous value one Excel digit position to the left. Adding the new character value appends the new digit in the least significant position.

Because Excel titles use positional notation with base 26 and digits 1 through 26, this update rule exactly matches the mathematical meaning of the title.

The algorithm starts from 0 and processes every character once, so after the final character, result equals the correct Excel column number.

Complexity

Let n be the length of columnTitle.

Implementation

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        result = 0

        for ch in columnTitle:
            value = ord(ch) - ord("A") + 1
            result = result * 26 + value

        return result

Code Explanation

Start with:

result = 0

Process each character:

for ch in columnTitle:

Convert the character into a number:

value = ord(ch) - ord("A") + 1

Examples:

Shift the previous digits left:

result = result * 26

Then append the new digit:

result = result + value

Combined:

result = result * 26 + value

Finally:

return result

returns the Excel column number.

Recursive Implementation

We can also solve this recursively.

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        if not columnTitle:
            return 0

        prefix = self.titleToNumber(columnTitle[:-1])
        current = ord(columnTitle[-1]) - ord("A") + 1

        return prefix * 26 + current

The iterative solution is simpler and avoids recursion overhead.

Testing

def run_tests():
    sol = Solution()

    assert sol.titleToNumber("A") == 1
    assert sol.titleToNumber("B") == 2
    assert sol.titleToNumber("Z") == 26
    assert sol.titleToNumber("AA") == 27
    assert sol.titleToNumber("AB") == 28
    assert sol.titleToNumber("AZ") == 52
    assert sol.titleToNumber("BA") == 53
    assert sol.titleToNumber("ZY") == 701
    assert sol.titleToNumber("ZZ") == 702
    assert sol.titleToNumber("AAA") == 703

    print("all tests passed")

run_tests()