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.size() 大小相同且出现在“word”之前的单词数。

准确地说，这个位:

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 函数计算二项式系数，即选择 k 个元素的方法数来自一组 n 个元素。此函数在您的评论中称为 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 是本例中第一个有效的第 3 个字符，desirableStart 会负责)。
5. 第三个字母是z，计算第3个字母的组合，从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;