Post date: Jul 06, 2013 6:6:53 AM
Problem
Imagine an alphabet of words. Example:
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.
Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.
Input Output
ab 27
ba 0
aez 441
Note: Brute-force is not allowed.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Print the index of a word with letters in ascending order -- Microsoft
Created Date : 06-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
bool IsValid(string str)
{
for(int i = 1; i < str.size(); ++i){
if(str[i] <= str[i - 1]) return false;
}
return true;
}
int NChooseK(int n, int k)
{
if (n == k || k == 0) return 1;
return NChooseK(n - 1, k) + NChooseK(n - 1, k - 1);
}
static int FindIndex(string str)
{
if(!IsValid(str)) return 0;
// count how many strings before string with str.size()
// C(26, 1) + C(26, 2) + ... + C(26, len - 1)
int index = 0;
int i = 1;
while(i < str.size()){
index += NChooseK(26, i);
i++;
}
char desirableStart;
i = 0;
while( i < str.size()){
desirableStart = (i == 0) ? 'a' : str[i - 1] + 1;
for(int j = desirableStart; j < str[i]; ++j){
index += NChooseK('z' - j, str.size() - i - 1); // Choose str.size() - i - 1 in the available charset
}
i ++;
}
index ++;
return index;
}
static void DoTest(string str)
{
cout << setw(10) << left << str;
cout << " ----> " << left << FindIndex(str) << endl;
cout << "--------------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("ab"); // 27
DoTest("ba"); // 0
DoTest("bc"); // 52
DoTest("aez"); // 441
DoTest("cde"); // 928
DoTest("cdb"); // 0
DoTest("cdf"); // 929
DoTest("moqx"); // 16983
DoTest("xyz"); // 2951
DoTest("hjmoqsu"); // 930152
return 0;
}
Output
ab ----> 27
--------------------------------
ba ----> 0
--------------------------------
bc ----> 52
--------------------------------
aez ----> 441
--------------------------------
cde ----> 928
--------------------------------
cdb ----> 0
--------------------------------
cdf ----> 929
--------------------------------
moqx ----> 16983
--------------------------------
xyz ----> 2951
--------------------------------
hjmoqsu ----> 930152
--------------------------------
Press any key to continue . . .