# LeetCode 171: Excel Sheet Column Number

## Problem Restatement

We are given an Excel column title:

```python
columnTitle
```

We need to return its corresponding column number.

Excel columns are labeled like this:

| Title | Number |
|---|---:|
| `"A"` | `1` |
| `"B"` | `2` |
| `"Z"` | `26` |
| `"AA"` | `27` |
| `"AB"` | `28` |
| `"ZY"` | `701` |

This problem is the reverse of LeetCode 168.

The input contains only uppercase English letters. The constraints guarantee the answer fits in a 32-bit integer. ([leetcode.com](https://leetcode.com/problems/excel-sheet-column-number/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Excel column title string |
| Output | Corresponding integer |
| Alphabet | Uppercase `A` through `Z` |
| Digit mapping | `A = 1`, ..., `Z = 26` |
| Important detail | No zero digit exists |

Example function shape:

```python
def titleToNumber(columnTitle: str) -> int:
    ...
```

## Examples

Example 1:

```python
columnTitle = "A"
```

Output:

```python
1
```

Example 2:

```python
columnTitle = "AB"
```

Compute:

```python
A = 1
B = 2
```

So:

```python
1 * 26 + 2 = 28
```

Return:

```python
28
```

Example 3:

```python
columnTitle = "ZY"
```

Compute:

```python
Z = 26
Y = 25
```

So:

```python
26 * 26 + 25 = 701
```

Return:

```python
701
```

## First Thought: This Is Like Base 26

This looks similar to converting a number written in base 26.

For example:

```text
"AB"
```

behaves like:

```text
1 * 26 + 2
```

But there is one important difference.

Normal base 26 digits are:

```text
0 through 25
```

Excel digits are:

```text
1 through 26
```

Still, the accumulation process is almost identical to normal positional notation.

## Key Insight

Process the string from left to right.

Suppose we already computed the value of the prefix.

When we read a new character, shift the old value left by one base-26 position:

```python
result *= 26
```

Then add the new digit value.

Character conversion:

```python
"A" -> 1
"B" -> 2
...
"Z" -> 26
```

We can compute this using ASCII codes:

```python
ord(ch) - ord("A") + 1
```

## Why the Formula Works

Suppose we process:

```python
"AB"
```

Start:

```python
result = 0
```

Read `"A"`:

```python
result = 0 * 26 + 1 = 1
```

Read `"B"`:

```python
result = 1 * 26 + 2 = 28
```

This matches the Excel column number.

The multiplication by `26` shifts previous digits one position to the left, exactly like decimal numbers use multiplication by `10`.

## Algorithm

Initialize:

```python
result = 0
```

For each character `ch` in `columnTitle`:

1. Convert the character into its numeric value.
2. Multiply `result` by `26`.
3. Add the digit value.

Return `result`.

## Walkthrough

Use:

```python
columnTitle = "ZY"
```

Start:

```python
result = 0
```

Read `"Z"`:

```python
value = 26
result = 0 * 26 + 26 = 26
```

Read `"Y"`:

```python
value = 25
result = 26 * 26 + 25 = 701
```

Return:

```python
701
```

## Correctness

The algorithm processes the column title from left to right.

Suppose after processing the first `k` characters, `result` equals the correct numeric value of that prefix.

When the next character is read, multiplying by `26` shifts the previous value one Excel digit position to the left. Adding the new character value appends the new digit in the least significant position.

Because Excel titles use positional notation with base `26` and digits `1` through `26`, this update rule exactly matches the mathematical meaning of the title.

The algorithm starts from `0` and processes every character once, so after the final character, `result` equals the correct Excel column number.

## Complexity

Let `n` be the length of `columnTitle`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan each character once |
| Space | `O(1)` | Only one accumulator is used |

## Implementation

```python
class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        result = 0

        for ch in columnTitle:
            value = ord(ch) - ord("A") + 1
            result = result * 26 + value

        return result
```

## Code Explanation

Start with:

```python
result = 0
```

Process each character:

```python
for ch in columnTitle:
```

Convert the character into a number:

```python
value = ord(ch) - ord("A") + 1
```

Examples:

| Character | Value |
|---|---:|
| `"A"` | `1` |
| `"B"` | `2` |
| `"Z"` | `26` |

Shift the previous digits left:

```python
result = result * 26
```

Then append the new digit:

```python
result = result + value
```

Combined:

```python
result = result * 26 + value
```

Finally:

```python
return result
```

returns the Excel column number.

## Recursive Implementation

We can also solve this recursively.

```python
class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        if not columnTitle:
            return 0

        prefix = self.titleToNumber(columnTitle[:-1])
        current = ord(columnTitle[-1]) - ord("A") + 1

        return prefix * 26 + current
```

The iterative solution is simpler and avoids recursion overhead.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.titleToNumber("A") == 1
    assert sol.titleToNumber("B") == 2
    assert sol.titleToNumber("Z") == 26
    assert sol.titleToNumber("AA") == 27
    assert sol.titleToNumber("AB") == 28
    assert sol.titleToNumber("AZ") == 52
    assert sol.titleToNumber("BA") == 53
    assert sol.titleToNumber("ZY") == 701
    assert sol.titleToNumber("ZZ") == 702
    assert sol.titleToNumber("AAA") == 703

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"A"` | First column |
| `"Z"` | Largest one-letter title |
| `"AA"` | First two-letter title |
| `"AB"` | Standard example |
| `"AZ"` | Ends with `Z` |
| `"BA"` | Carries into next leading digit |
| `"ZY"` | Standard larger example |
| `"ZZ"` | Largest two-letter title |
| `"AAA"` | First three-letter title |