Excel Sheet Column Number - Leetcode Solution

Problem Statement:

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

Solution:

We need to convert a given Excel sheet column title to its corresponding column number. We can do this by treating each character in the title as a digit in a base-26 number system (with digits ranging from 1 to 26 rather than 0 to 25).

We start at the rightmost position, treat the character here as the least significant digit, and multiply its value by 26^(0) (which is just 1). We then move one position to the left, treat that character as the next least significant digit, and multiply its value by 26^(1) (which is 26). We continue this process until we reach the leftmost character, which is the most significant digit.

For example, let's consider the column title "AB". We start at the rightmost position, which is "B". The value of "B" is 2 (since it's the 2nd letter of the alphabet), so we multiply 2 by 26^(0) to get 2. We then move one position to the left, which brings us to "A". The value of "A" is 1, so we multiply 1 by 26^(1) to get 26. Finally, we add these results together to get 28, which is the column number for "AB".

Now, let's see the implementation of the above approach in code.

Code:

class Solution { public int titleToNumber(String s) { int result = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int value = c - 'A' + 1; // get the value of the character result = result * 26 + value; // multiply by 26 and add to the result } return result; } }

In the above code, we iterate through each character in the input string. We get the value of each character by subtracting the ASCII value of 'A' from the ASCII value of the character and adding 1 (since 'A' has a value of 1, not 0). We then multiply the current result by 26 and add the value of the current character to get the new result. Finally, we return the result once we've processed all the characters.

Time Complexity:

The time complexity of the above code is O(n) where n is the length of the input string. We perform a constant amount of work for each character in the string, so the total amount of work is proportional to the length of the string.

Space Complexity:

The space complexity of the above code is O(1) since we only use a constant amount of extra space (for the result variable).

1