algorithm - 用字母表表示一个单词

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.

这样的字符序列只需按升序排列(ab 有效，但 ba 无效)。给定任何单词，如果有效则打印其索引，如果无效则打印 0。

Input Output
ab 27
ba 0
aez 441

注意:不允许暴力破解。这是问题的链接:http://www.careercup.com/question?id=21117662

我可以将该解决方案理解为:

• 总字数为 2^26 -1。
• 对于给定的单词，尺寸较小的单词首先出现。
• 设 n 为单词的长度，
  • 大小小于 n 的单词总数为 C(26, 1) + C(26, 2) + ...+ C(26, n -1)
• 然后计算给定单词之前有多少个相同大小的单词
• 两个数加一就是结果

引用:sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft

在示例解决方案中，我了解了作者如何计算大小小于 word.size() 的单词数。但是，在代码中，我不太确定如何查找出现在“word”之前的与 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函数计算二项式系数，即从一组 n 个元素中选择 k 个元素的方法数。该函数被称为C(n, k)在您的评论中，所以我将使用相同的符号。

由于字母已排序且不重复，因此这正是创建问题中描述的 n 字母单词的方法数，因此这就是函数的第一部分是的原因让您处于正确的位置:

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 .

此时，您已经有了 n 字母单词的初始索引，并且需要查看需要跳至多少个 n 字母单词的组合到达单词的末尾。为此，您必须检查每个单独的字母，并计算所有可能的字母组合，该组合以前一个字母之后的一个字母(代码中的 desirableStart 变量)开始，并以正在检查的字母结束。

例如，对于 aez您将按照以下步骤进行:

1. 获取最后一个 2 字母单词索引 ( yz )。
2. 将索引增加一(这实际上是在代码末尾完成的，但在这里这样做以保持正确的位置更有意义):现在我们的索引为 abc .
3. 第一个字母是 a ，无需增加。您还在abc .
4. 第二个字母是 e ，计算 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;