面試題：五筆的字典序編碼與解碼

前幾天朋友跟我說了一道面試題：五筆的編碼範圍是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

再後來，我聯系到了以前的一道題目：判斷回文數時用到的數字反轉的技巧。

好像有底了，寫個代碼如下：

// 按長度排序的串索引，忽略錯誤檢查

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;
	}
}
            
// 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. 前幾天，又在某網站上碰到判斷回文數的問題，我還是按老辦法，開一個大數組，将數字一個個的拆到數組裡面去，然後依次判斷數組是否對稱；看了答案，才枉然大悟；但是這個答案我在一年前，二年前...，六年前，就已經重複的看過了，真的是看過就忘，忘了就又回到最初學習程式設計時候的思路去了。工作時候，寫的代碼洋洋灑灑；自我感覺也不差，但是遇到這些問題時候，老是分析不出最優方案。
 

 
程式設計，真的不容易把握。