再present与字母词 [英] Represent a word with an alphabet

问题描述

这是一个面试问题：

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是有效的，但巴不是）。鉴于任何文字打印和0的索引，如果有效，如果没有。

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

注：蛮力是不允许的。这里是链接到的问题： http://www.careercup.com/question?id=21117662

我可以理解，解决方案：

I can understand that solution as:

• 在总的话来说就是2 ^ 26 -1。
• 对于一个给定的单词，具有体积小的话先发生。
• 设n是该字的长度，
  • 与大小小于n词总数为C（26，1）+ C（26，2）+ ... + C（26，N-1）
  • The total words is 2^26 -1.
  • For a given word, the words with small size occurs first.
  • Let n be the length of the word,
    • Total number of words with size less than n is C(26, 1) + C(26, 2) + ...+ C(26, n -1)

    参考： sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft

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

    在样品溶液，我知道如何的话，大小小于word.size笔者计算出的数字（）。但是，在code，我也不太清楚如何找到同样大小的字前发生的）词作为word.size（的数量。

    In the sample solution, I understood how the author calculated number of words with size less than word.size(). But, in the code, I am not too sure about how to find number of words of the same size as word.size() that occur before 'word'.

    precisely，该位：

    Precisely, this bit:

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

    有人可以帮助我理解这一点？谢谢你。

    Can someone help me understand this bit? Thanks.

    推荐答案

    首先（你可能得到这部分，但为了完整起见），在 NChooseK 函数计算二项式系数，即路的数目来选择的 K 的从一组的 N 的元素的元素。该功能被称为 C（N，K）在您的意见，所以我将使用相同​​的符号。

    First of all (you probably got this part, but for completeness sake), the NChooseK function calculates the binomial coefficient, i.e. the number of ways to choose k elements from a set of n elements. This function is referred to as C(n, k) in your comments, so I will use the same notation.

    由于字母排序和不重复，这正是方式之一可以创建数的 N 的-letter中所述问题的话，那么，这是为什么该函数的第一部分是让你在正确的位置上：

    Since the letters are sorted and not repeating, this is exactly the number of ways one can create the n-letter words described in the problem, so this is why the first part of the function is getting you at the right position:

    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

    For example, if your input was aez, this would get the index of the word yz, which is the last possible 2-letter combination: C(26, 1) + C(26, 2) = 351.

    在这一点上，你有你的 N 的-letter单词的首索引，需要看多少组合的 N 的-letter你需要跳到话得到的字的末尾。要做到这一点，你必须检查每个字母和计数的开始之后，previous一个字母，字母的所有可能的组合之一（在$ c中的 desirableStart 变量$ c）中，并用字母结尾被检查

    At this point, you have the initial index of your n-letter word, and need to see how many combinations of n-letter words you need to skip to get to the end of the word. To do this, you have to check each individual letter and count all possible combinations of letters starting with one letter after the previous one (the desirableStart variable in your code), and ending with the letter being examined.

    例如，对于 AEZ 您将着手如下：

    For example, for aez you would proceed as following:

    1. 获得最后2个字母的单词索引（ YZ ）。
    2. 加一指数（这实际上是做在你的code结束，但它更有意义，这样做在这里，以保持正确的位置）：现在我们正处于的指数ABC 。
    3. 在第一个字母是 A ，无需增加。你还在为农行。
    4. 第二个字母电子，算上组合第二信 B 到电子。这将让你 AEF （注意， F 在这个例子中，第一个有效的第三个字符，而 desirableStart 照顾的）。
    5. 第三个字母是以Z ，算上组合第三个字母，从 F 到ž 。这将让你 AEZ 。
    1. Get the last 2-letter word index (yz).
    2. Increase index by one (this is actually done at the end of your code, but it makes more sense to do it here to keep the correct positions): now we are at index of abc.
    3. First letter is a, no need to increase. You are still at abc.
    4. Second letter is e, count combinations for 2nd letter from b to e. This will get you to aef (note that f is the first valid 3rd character in this example, and desirableStart takes care of that).
    5. Third letter is z, count combinations for 3rd letter, from f to z. This will get you to aez.

    这就是你的code中的最后一部分的作用：

    That's what the last part of your code does:

    // 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;
    

    这篇关于再present与字母词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！