[LeetCode Road] Excel Sheet Column Number - Solution/C++

171. Excel Sheet Column Number

Question:

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

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

Example:

Input: "A"
Output: 1

Input: "AB"
Output: 28

Input: "ZY"
Output: 701

Constraints:

1 <= s.length <= 7

s consists only of uppercase English letters.

s is between "A" and "FXSHRXW".

Source code:

Version 1

Idea:
The type of input is string, so we need to split it into characters, and convert character to demical by using ASCII talbe.

Each digit will times 26 to the power of (len - i - 1).
Why is (len - i - 1) means? If input is "AB" (len=2), we get "A" character first, and "A" is tens digit, so use the fourmula (2 - 0 - 1) the power is 1,then you can get 26. pow(26, 1) * (65 - 64)
Furthermore, the next character is "B", the power is 0, so you get 2. pow(26, 0) * (66-64)
Hence, the results is 28 (26+2).

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int titleToNumber(string s) {
        const int len = s.length();
        int res = 0;
        for(int i = 0; i < len; i++){
            res += pow(26, len - i - 1) * ((int)s[i] - 64);
        }
        return res;
    }
};

Version 2

Idea:
The runtime of Version 2 will get more faster than Version 1. Because it's not use pow() function.

A logic likes : (previous_sum * 26 + current_sum), so the sum times 26 for each loop (= each digit)

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int titleToNumber(string s) {
        int ln = s.length();
        int sum = 0;
        for(int i = 0; i<ln;i++){
            sum = sum * 26 + (int(s[i])-64);
        }

        return sum;
    }
};