Excel Sheet Column Number

Patrick Leaton

Published: March 19, 2021, 11:04 p.m.

Problem 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

Constraints:

1 <= s.length <= 7
s consists only of uppercase English letters.
s is between "A" and "FXSHRXW".

The description was taken from https://leetcode.com/problems/excel-sheet-column-number/.

Problem Solution

#O(N) Time, O(1) Space

class Solution:

def titleToNumber(self, s: str) -> int:

result = 0

for char in s:

result *= 26

result += (ord(char) - ord('A') + 1)

return result

Problem Explanation

If we're given a problem with a weird ordering that we're needing to convert, typically a dictionary is a good approach.

We could solve this problem by using a dictionary that maps each character to their order in the alphabet and then multiplying them by their base twenty-six index in the string since the alphabet is twenty-six letters long. We would then add the values together to get the column number.

That would require linear space, however.

A constant space, one pass approach would be to utilize ASCII values and to build the result from left to right.

Let's first initialize the resulting integer that we will be returning.

result = 0

Afterward, we will traverse the characters within the string.

for char in s

Before we add the value of each letter, we will first multiply the result by twenty-six to set a placeholder for the next most significant digit. We are building the number left to right, from most significant digit to least.

This is like how we would multiply an output integer by ten during each iteration if we were manually converting a number string to an integer.

result *= 26

After setting our placeholder, we will add the value of the character in our iteration by subtracting the order of its ASCII value by the order of"A", since these are all capital characters we are dealing with.

We will need to add one before adding it to get the actual order.

For example, "A" has an ASCII value of sixty-five. If we were to get "A" as input and subtract the order by itself, we would have sixty-five minus sixty-five, which equals zero.

We want to have one, its order.

result += (ord(char) - ord('A') + 1)

After we have converted all the character values and added them to the output, we will return the result.

return result