面试题：五笔的字典序编码与解码（转）

（转自http://blog.csdn.net/jiangnanyouzi/article/details/6827534）

前几天朋友跟我说了一道面试题：五笔的编码范围是a到y的25个字母，从1位到4位的编码，

如果将五笔的编码按字典序排序，形成数组如下：a, aa, aaa, aaaa, aaab, aaac, ..., b, ba, baa, baaa, baab...yyyx, yyyy

其中a的索引是0，aa的索引是1，aaa的索引是2，aaaa的索引是3，以此类推：

1）、编写一个函数，输入是任意一个合法的字符串，输出这个字符串对应的索引；

2）、编写一个函数，输入是任意一个合法的索引，输出这个索引对应的字符串。

朋友还给我他当时的代码，我看了代码大概20分钟，还不知道他是怎么入手的；然后我就问他：你怎么想到思路的，他说：很自然啊，排列组合！

再想了一会，才领悟过来：差距啊，这就是差距。

记下思路，作个思路备用库也是好的【以下思路是我事后诸葛亮似的小结，但也算是一个思路吧】

注意到：如果都是4字符的定长串的话，很简单，就是25进制的一个表示法，但这里是不定长的。

1、观察头几个串：a-->0, aa->1, aaa->2，aaaa->3：应该可以看出来，这里的索引就是：字符串长度 - 1

2、已知a的索引，求b的索引：因为a到b之间隔了以下四种情况的字符串：a后跟2字符的串有25个（aa，ab，...ay），a后跟2字符的串有25*25个(aaa, aab, ... ayy)，a后面跟3字符的串有25*25*25个(aaaa,aaab,...ayyy)，然后才是b，所以b的索引 = a的索引 + 25+25*25+25*25*25 + 1，加1是因为b排在a和中间的字符之后1个

3、已知aa的索引，求ab的索引：同理，ab的索引 = aa索引 + 25 + 25* 25 + 1

4、已知aaa的索引，求aab的索引：同理，aab的索引 = aaa索引 + 25 + 15、已知aaaa的索引，求aaab的索引 = aaaa索引 + 1

至于aaaa，aaa，aa, a的索引由1: 可归纳为 字符串长度 - 1

所以：可用一个权重数组来表示修正后的进制：factor[4] = {1+25+25*25+25*25*25, 1+25+25*25, 1+25, 1}

然后字符串string的索引函数为：index(string) = (string.length - 1) + sum[ factor[i] * (string[i] - 'a') ,  {i, 0, string.length-1 } ]

其中sum是对内部表达式求和。

 

 

int encode(const char *str)
{
    int len = 0;
    int index = 0;
    int factor[] = {1+25+25*25+25*25*25, 1+25+25*25, 1+25, 1};
    while(*str)
        index += factor[len++] * (*str++ - 'a');
    return index + (len - 1);
}

 

 

二、解码：解码过程就是编码过程的逆过程，有了factor数组，就简单多了

 

 

// dst为至少5字符的字符数组
void decode(char *dst, int index)
{
    int i = 0;
    int factor[] = {1+25+25*25+25*25*25, 1+25+25*25, 1+25, 1};
    while(index >= 0)
    {
        *dst++ = 'a' + index / factor[i];
         index %= factor[i++];
        --index; // 此处要减1，还原到下一个字符
    }
    *dst = '\0';
}

 

三、变形：这个问题在朋友的帮助下理清思路之后，我就在想，五笔编码是越常用的字串长越少，按道理是不应该按字典排序的，应该按字母的长短排序比较好：

a, b, ... x, y, aa, ab, ... yy, aaa, aab, ..., yyy, aaaa, aaab, ..., yyyy；如果这样排序，那么索引就好像简单多了？

起码可以按串长来分索引，比如长度为1的串范围[0, 25-1], 长度为2的串范围[25, 25*25-1]，以此类推。

但如果不用分段，还有什么办法呢？

最初，我按照上面的思路分析：a到b的距离为1，aa到ab的距离也为1，好像得不到factor数组。

后来，我观察到上面的数组：a的索引为0，aa的索引为25，a和a的差距是0，到第二位了就变成了1*25；再看ba的索引50，b和a的差距是1，到第二位了就变成2*25

再后来，我联系到了以前的一道题目：判断回文数时用到的数字反转的技巧。

好像有底了，写个代码如下：

// 按长度排序的串索引，忽略错误检查

<pre name="code" class="cpp"><pre name="code" class="cpp"><pre name="code" class="cpp">int encode(const char *str)
{
    int index = *str++ - 'a';
    while(*str)
        index = 25 * (1 + index) + (*str++ - 'a');
    return index;
}

验证了一下，发现是对的，嗯，不用分长度求值了。

 

 

解码过程也是上述过程的逆过程，不过要反转字符串：

 

// 反转字符串str
void ReverseStr(char *str)
{
    int i;
    int len = strlen(str);
    for(i = 0; i < len / 2; ++i)
    {
        char c = str[i];
        str[i] = str[len - 1 - i];
        str[len - 1 - i] = c;
    }
}
<span style="font-family: monospace; white-space: pre; background-color: rgb(240, 240, 240); "></span><pre name="code" class="cpp">

</pre><pre name="code" class="cpp"><span style="font-family: monospace; white-space: pre; background-color: rgb(240, 240, 240); "></span><pre name="code" class="cpp"><pre name="code" class="cpp"><pre name="code" class="cpp">// dst为至少5字符的字符数组
void decode(char *dst, int index)
{
    int j;
    char *p = dst;
    while(index >= 0)
    {
        *p++ = 'a' + index % 25;
        index = index / 25 - 1;
    }
    *p = '\0';
    ReverseStr(dst);
}

四、现实：如果在实际应用中，有这样的需求，还是用长度排序的串比较好，又由于用户一天内使用的汉字基本有限，用哈希将用户输入的串缓冲起来，效率更高。

五、初衷：写这篇文章，主要是感觉编程实际上并不是那么容易，尤其是编程思维的把握上，很容易出错。感到有点不大可控，于是趁现在还记起思路时候，将其记下来，以便于未来时不时查看。另外，如果各位有更好的思路，希望大家能告知。

 

 

PS. 前几天，又在某网站上碰到判断回文数的问题，我还是按老办法，开一个大数组，将数字一个个的拆到数组里面去，然后依次判断数组是否对称；看了答案，才枉然大悟；但是这个答案我在一年前，二年前...，六年前，就已经重复的看过了，真的是看过就忘，忘了就又回到最初学习编程时候的思路去了。工作时候，写的代码洋洋洒洒；自我感觉也不差，但是遇到这些问题时候，老是分析不出最优方案。