algoadvance

Leetcode 171. Excel Sheet Column Number

Problem Statement

You are given a string columnTitle that represents the column title as appear in an Excel sheet. For example:

• “A” -> 1
• “B” -> 2
• …
• “Z” -> 26
• “AA” -> 27
• “AB” -> 28
• …

You need to return its corresponding column number.

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”].

Clarifying Questions:

1. Q: Should the result be an integer that matches the Excel column numbering system? A: Yes.

2. Q: Are there any special characters in columnTitle? A: No, columnTitle consists only of uppercase English letters.

3. Q: Can the input be an empty string? A: No, the constraints ensure that columnTitle.length is at least 1.

Strategy:

• Each letter in the string represents a digit in a 26-base number.
• The letter ‘A’ corresponds to 1, ‘B’ to 2, …, ‘Z’ to 26.
• We can convert the column title to a number similarly to how we convert a string representing a decimal number to an integer.

To convert each character in columnTitle into its corresponding number:

• Calculate its value relative to ‘A’ (i.e., value = character - 'A' + 1).
• Multiply the current result by 26 (since it’s a base-26 number) and add the value of the current character.

This can be visualized with the example “AB”:

• For ‘A’: Value is 1. Initial result is 0, so 0 * 26 + 1 = 1.
• For ‘B’: Value is 2. Current result is 1, so 1 * 26 + 2 = 28.

Code:

public class Solution {
    public int titleToNumber(String columnTitle) {
        int result = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            char c = columnTitle.charAt(i);
            int value = c - 'A' + 1;
            result = result * 26 + value;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test cases
        System.out.println(sol.titleToNumber("A")); // 1
        System.out.println(sol.titleToNumber("AB")); // 28
        System.out.println(sol.titleToNumber("ZY")); // 701
    }
}

Time Complexity:

The time complexity of the solution is O(n), where n is the length of the columnTitle string. This is because we are processing each character in the string exactly once.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?