171. Excel Sheet Column Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 57.1%
Problem Breakdown
The problem requires converting an Excel column title into its corresponding column number. The input is a string columnTitle that represents the column title in the format used by Excel sheets (e.g., “A”, “B”, …, “Z”, “AA”, “AB”, etc.). The output is an integer representing the column number.
Inputs:
- A string
columnTitleconsisting of uppercase English letters.
Outputs:
- An integer representing the column number.
Implicit Constraints or Tricky Edge Cases:
- The length of
columnTitleis between 1 and 7. - The input consists only of uppercase English letters.
- The problem does not specify handling for invalid inputs, but we can assume that the input will always be valid as per the constraints.
Intuition
The brute-force approach would involve iterating through all possible column titles up to the given title and counting them. However, this is inefficient with a time complexity of O(n^2) where n is the length of the string, which is not suitable for large inputs.
A better approach involves recognizing that the problem is similar to converting a number from base-26 to base-10. Each character in the string represents a digit in base-26, and we need to convert this to its decimal equivalent.
Approach
To solve this problem efficiently, we can use a mathematical approach:
- Initialize a variable
resultto 0. - Iterate through each character in the string from left to right.
- For each character, calculate its value by subtracting the ASCII value of ‘A’ and adding 1 (since ‘A’ corresponds to 1).
- Multiply the current
resultby 26 (to shift the previous digits one place to the left) and add the calculated value of the current character. - Return the final
result.
This approach leverages the fact that each position in the string represents a power of 26, similar to how each position in a decimal number represents a power of 10.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string. We iterate through each character once.
- Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def titleToNumber(columnTitle: str) -> int:
result = 0
for char in columnTitle:
value = ord(char) - ord('A') + 1
result = result * 26 + value
return result
Edge Cases Handled
- Single Character Input: The code correctly handles single-character inputs like “A” which should return 1.
- Multi-Character Inputs: The code handles multi-character inputs like “AB” and “ZY” by treating each character as a digit in base-26.
- Maximum Length Input: The input can be up to 7 characters long, and the code correctly computes the column number for such cases.
- Boundary Conditions: The problem specifies that the input will always be valid, so no additional checks are needed for invalid inputs.