Leetcode: 171. Excel Sheet Column Number

Converting Excel Column Titles to Numbers in C++

Introduction: In this blog post, we'll explore a simple C++ solution to the problem of converting Excel column titles to their corresponding column numbers. Given a string columnTitle, representing the column title as it appears in an Excel sheet, we will implement a function that returns the corresponding column number. Understanding this conversion can be useful in various scenarios, such as parsing data from Excel files or working with spreadsheet data programmatically.

Problem Description: The problem can be defined as follows: Given a string columnTitle, which represents the column title in Excel, we need to convert it into its corresponding column number. Excel column titles consist of one or more uppercase letters, and each letter corresponds to a digit in base 26. The letters are mapped to numbers in the following way: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. If there are multiple letters, the title is evaluated from left to right, with each letter contributing to the column number in its respective position.

Approach: To solve this problem, we will implement a function called titleToNumber, which takes a string columnTitle as input and returns the corresponding column number as an integer.

class Solution {
public:
    int titleToNumber(std::string s) {
        int result = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            result = result * 26;
            // In C++, subtracting characters is also subtracting ASCII values of characters
            result += (s[i] - 'A' + 1);
        }
        return result;
    }
};

Time Complexity: Let's analyze the time complexity of the titleToNumber function:

1. The function iterates over each character of the input string columnTitle exactly once using a for loop.
2. Within the loop, all operations (addition, subtraction, and multiplication) are constant-time operations.
3. Therefore, the time complexity of the titleToNumber function is O(N), where N is the length of the input string columnTitle.

Example: Let's illustrate the implementation with an example. Consider the column title "AB":

1. Initially, result = 0.
2. For the first character 'A', result = 0 * 26 + (65 - 65 + 1) = 1.
3. For the second character 'B', result = 1 * 26 + (66 - 65 + 1) = 28.

So, the column number corresponding to the title "AB" is 28.

Conclusion: We have successfully implemented a C++ solution to convert Excel column titles to their corresponding column numbers. The provided function, titleToNumber, efficiently handles the conversion with a time complexity of O(N), where N is the length of the input string. By understanding this conversion process and its time complexity, you can work with Excel data more effectively in your C++ programs. Whether you're parsing Excel files or dealing with spreadsheet data programmatically, this knowledge can prove invaluable in various scenarios. Happy coding!