## Tuesday, March 31, 2015

### LeetCode OJ - Excel Sheet Column Number

Problem:

Solution:

As you will be able to read from the code - the algorithm is pretty simple. The key idea is to understand how did I get there (i.e. the thought process).

If it is possible at all, I would start any problem from its simplest case. In this particular example, a single letter problem is quite simple, isn't it? So all we need to do is to have s[0] - 'A' + 1 and we are done.

Now we start with the second letter. I knew if I know how to do "AA", it is simply the next of "Z", which is 27. "AZ" is 52, therefore "BA" is 53. I conjectured that it is just the second digit times 26 + the first digit, and it is indeed the case, because for the second character to advance, the first character must have gone through 'A' - 'Z', which is 26 characters.

The rest follows.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/excel-sheet-column-number/

#include "LEET_EXCEL_SHEET_COLUMN_NUMBER.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_EXCEL_SHEET_COLUMN_NUMBER
{
class Solution
{
public:
int titleToNumber(string s)
{
int result = 0;
int digitFactor = 1;
for (int i = s.length() - 1; i >= 0; i--)
{
result += (s[i] - 'A' + 1) * digitFactor;
digitFactor *= 26;
}

return result;
}
};
};

using namespace _LEET_EXCEL_SHEET_COLUMN_NUMBER;

int LEET_EXCEL_SHEET_COLUMN_NUMBER()
{
Solution solution;
cout << solution.titleToNumber("A") << endl;
cout << solution.titleToNumber("Z") << endl;
cout << solution.titleToNumber("AA") << endl;
cout << solution.titleToNumber("AZ") << endl;
cout << solution.titleToNumber("BA") << endl;
cout << solution.titleToNumber("ZZ") << endl;
cout << solution.titleToNumber("AAA") << endl;
cout << solution.titleToNumber("AAZ") << endl;
cout << solution.titleToNumber("ABA") << endl;
cout << solution.titleToNumber("AZZ") << endl;
cout << solution.titleToNumber("BAA") << endl;
return 0;
}