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 : 08-08-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
/**
* Check if input str is valid
* @param str input word
* @return ture if valid, otherwise return false
*/
bool IsValid(const string& str)
{
if(str.size() < 1) return false;
for(int i = 1; i < str.size(); ++i){
if(str[i] < 'a' || str[i] > 'z') return false;
if(str[i - 1] < 'a' || str[i - 1] > 'z') return false;
if(str[i] <= str[i - 1]) return false;
}
return true;
}
/**
* Calculate bionomial coefficients n choose k
* @param n set number
* @param k number to choose
* @return bionomical coefficients
*/
int NChooseK(int n, int k)
{
assert(n > 0);
assert(k >= 0);
assert(n >= k);
if (n == k || k == 0) return 1;
return NChooseK(n - 1, k) + NChooseK(n - 1, k - 1);
}
/**
* Calculate the index of input string
* @param str input string
* return 0 if input is not invalid otherswise return the index
*/
static int FindIndex(const string& str)
{
// Check if input is valid
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++;
}
// Count how many string with same length ahead
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;
}
/**
* Test input string
* @param str input string
*/
static void DoTest(string str)
{
assert(str.size() > 0);
cout << setw(10) << left << str;
cout << " ----> " << left << FindIndex(str) << endl;
cout << "--------------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("ab"); // Expect 27
DoTest("ba"); // Expect 0
DoTest("bc"); // Expect 52
DoTest("aez"); // Expect 441
DoTest("cde"); // Expect 928
DoTest("cdb"); // Expect 0
DoTest("cdf"); // Expect 929
DoTest("moqx"); // Expect 16983
DoTest("xyz"); // Expect 2951
DoTest("hjmoqsu"); // Expect 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 . . .