算法:打印字符序列的正确索引

Question

我在准备考试时遇到了以下问题:

想象一下单词的字母.例:

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 

如何解决这个问题的任何指针将不胜感激.

Answer 1

让我给你一些提示:

• 你能找到给定长度的这类词的数量的公式k吗？
• 现在修一个长度k和一个字母l.有多少长度的字k开始l他们是谁？

提示:Pascal三角形.如果您需要更多提示,http://en.wikipedia.org/wiki/Combinadic可以提供帮助.如果你需要一些实现,你可以从(Python语言)中定义的rank函数中获得灵感https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py