algoadvance

Leetcode 171. Excel Sheet Column Number

Problem Statement

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number. For example:

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the columnTitle string?
    • Will the string always be in uppercase?
  2. Output Constraints:
    • Should the function return an integer corresponding to the column number?

Strategy

This problem is analogous to converting a number from a base-26 numeral system to a decimal (base-10) numeral system.

  1. Understanding the Mapping:
    • The character ‘A’ maps to the number 1, ‘B’ maps to 2, …, ‘Z’ maps to 26.
    • For multi-character strings, it follows a positional system similar to base-10 numbers but with base-26.
      • For example “AB”:
        • ‘A’ = 1, but as it’s the first character from the left, it represents (26^1) * 1.
        • ‘B’ = 2, and as the second character, it represents (26^0) * 2.
  2. Algorithm:
    • Initialize a variable to store the resultant number.
    • Traverse the string from left to right.
    • For each character, calculate its contribution based on its position.
  3. Steps:
    • Initialize result = 0.
    • Iterate over each character in the string.
      • Convert the character to its corresponding base-26 value.
      • Update result with the current character’s positional value.
    • Return the final result.

Code

#include <iostream>
#include <string>

int titleToNumber(const std::string& columnTitle) {
    int result = 0;
    for (char c : columnTitle) {
        int value = c - 'A' + 1;
        result = result * 26 + value;
    }
    return result;
}

int main() {
    std::string columnTitle = "AB"; // Example input
    std::cout << "The column number is: " << titleToNumber(columnTitle) << std::endl;
    return 0;
}

Time Complexity

This method ensures that the algorithm runs efficiently even for longer column titles, adhering to a linear time complexity.

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