Представляют слово с алфавитом

Question

Это вопрос интервью:

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. 

Такими, что последовательность символов должна быть только в порядке возрастания (абы допустимы, но ба не является). Если какое-либо слово печатает свой индекс, если он действителен и 0, если нет.

Input Output 
ab 27 
ba 0 
aez 441 

Примечание: Грубая сила не допускается. Вот ссылка на вопрос: http://www.careercup.com/question?id=21117662

Я могу понять, что решение, как:

• Итоговые слов равно 2^26 -1.
• Для данного слова сначала слова с небольшим размером.
• Пусть п длина слова,
  • Общее количество слов с размером меньшим, чем п представляет собой С (26, 1) + С (26, 2) + ... + С (26, п - 1)
• Затем рассчитать, как много слов с одинаковым размером до заданного слова
• сумма двух чисел plusing один является результатом

Ссылка: sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder - microsoft

В образце решения я понял, как автор рассчитал количество слов с размером меньше слова.size(). Но в коде я не слишком уверен в том, как найти число слов такого же размера, как word.size(), которые встречаются перед словом.

Именно этот бит:

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

Может кто-то помочь мне понять этот бит? Благодарю.

Answer 1

Прежде всего (вы, вероятно, получили эту часть, но для полноты), функция NChooseK вычисляет биномиальный коэффициент, то есть число способов выбрать к элементов из множества п элементов. Эта функция в ваших комментариях называется C(n, k), поэтому я буду использовать те же обозначения.

Поскольку буквы отсортированы и не повторяются, это точно количество способов создания слов, описанных в этой проблеме, поэтому именно поэтому первая часть функции - Правильное положение:

int index = 0; 
int i = 1; 

while(i < str.size()) { 
    // choose *i* letters out of 26 
    index += NChooseK(26, i); 
    i++; 
} 

Например, если ваш вход был aez, это было бы получить индекс слова yz, который является последним возможным 2-сочетание букв: C(26, 1) + C(26, 2) = 351.

На данный момент, у вас есть начальный индекс вашего п -Письма слова, и нужно, чтобы увидеть, сколько комбинаций из п -Письма слов, которые необходимо пропустить, чтобы добраться до конца слова. Для этого вам нужно проверить каждую отдельную букву и подсчитать все возможные комбинации букв, начиная с одной буквы после предыдущей (переменная desirableStart в вашем коде) и заканчивая проверкой письма.

Например, для aez вы выполните следующие действия:

1. Получить последний индекс слово 2 букв (yz).
2. Увеличьте индекс на единицу (это действительно делается в конце вашего кода, но имеет смысл сделать это здесь, чтобы сохранить правильные позиции): теперь мы находимся под индексом abc.
3. Первое письмо - a, не нужно увеличивать. Вы все еще находитесь в abc.
4. Второе письмо - e, комбинации комбинаций для 2-й буквы от b до e. Это приведет вас к aef (обратите внимание, что f является первым допустимым третьим символом в этом примере, и desirableStart позаботится об этом).
5. Третья буква - z, комбинации комбинаций для третьей буквы, от f до z. Это приведет вас к aez.

Вот что делает последнюю часть кода:

// get to str.size() initial index (moved this line up) 
index ++; 

i = 0; 
while(i < str.size()) { 

    // if previous letter was `e`, we need to start with `f` 
    desirableStart = (i == 0) ? 'a' : str[i - 1] + 1; 

    // add all combinations until you get to the current letter 
    for (int j = desirableStart; j < str[i]; ++j) { 

     char validLettersRemaining = 'z' - j; 
     int numberOfLettersToChoose = str.size() - i - 1; 
     index += NChooseK(validLettersRemaining, numberOfLettersToChoose); 
    } 

    i++; 
} 

return index; 

Answer 2

нет никакой разницы между вычислением количества слов такого же размера и контрагента для более коротких слов.

Вы можете быть сбиты с помощью индексирования массивов в c, начинающегося с 0. Таким образом, хотя i < str.size() может предложить иначе, последняя итерация этого цикла фактически считает слова того же размера, что и слова, индекс которого вычисляется ,