Tuesday, March 31, 2015

LeetCode OJ - Excel Sheet Column Number

Problem:

Please find the problem here.

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;
}

No comments :

Post a Comment