algoadvance

You are given a string columnTitle that represents the column title as appears in an Excel sheet.

For example:

  A -> 1
  B -> 2
  C -> 3
  ...
  Z -> 26
  AA -> 27
  AB -> 28 
  ...

You need to return the corresponding column number.

Example:

Input: columnTitle = "A"
Output: 1

Input: columnTitle = "AB"
Output: 28

Input: columnTitle = "ZY"
Output: 701

Constraints:

• 1 <= columnTitle.length <= 7
• columnTitle consists only of uppercase English letters.
• columnTitle is always a valid Excel column title.

Clarifying Questions

1. Will columnTitle always be a non-empty string?
   • Yes, according to the constraints, the minimum length is 1.
2. Can we assume all inputs are valid Excel column titles?
   • Yes, the constraints guarantee valid titles consisting of only uppercase letters.

Strategy

To solve this problem, we can consider the string as if it were a number in base-26, where ‘A’ corresponds to 1, ‘B’ to 2, …, and ‘Z’ to 26.

Let’s break this down step-by-step:

1. Initialize a result variable to 0.
2. Iterate through each character in the string.
3. For each character, convert it to its corresponding number using the formula: ord(character) - ord('A') + 1.
4. Accumulate this number into result by repeatedly multiplying the current result by 26 (like shifting digits left in decimal system) and adding the new value.

Example Walkthrough:

For “AB”, we compute it as follows:

• Start with result = 0.
• For ‘A’ (first character): ord('A') - ord('A') + 1 = 1 Update result: result = 0 * 26 + 1 = 1
• For ‘B’ (second character): ord('B') - ord('A') + 1 = 2 Update result: result = 1 * 26 + 2 = 28
• Final result is 28.

Code

def titleToNumber(columnTitle: str) -> int:
    result = 0
    for char in columnTitle:
        result = result * 26 + (ord(char) - ord('A') + 1)
    return result

# Test cases
print(titleToNumber("A"))   # Output: 1
print(titleToNumber("AB"))  # Output: 28
print(titleToNumber("ZY"))  # Output: 701

Time Complexity

The time complexity of this solution is O(n), where n is the length of the columnTitle. This is because we only traverse the string once, performing constant time operations for each character.

Try our interview co-pilot at AlgoAdvance.com

• 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?