这是很久以前遇到一个面试题，通讯录联系人拼音匹配算法，题目描述如下：
在通讯录里搜索联系人里，用户习惯使用拼音缩写，我们定义如下的搜索匹配规则：
以搜索王海宝（WangHaiBao）为例，如下输入均能够匹配到该人（注意：举例只是为阅读方便，实际实现不区分大小写）：
1）每字的首字母缩写：W，WH，WHB
2）每字或者全拼或者首字母：WH，WangH符合规则，但WanH，WanH，WangHaB不可
3）要顺序出现：WHB可以，HB，HBao不可
4）最后的输入部分可以是部分：WHBa，但WHBo不可
请编程实现该匹配算法，要求：
1）根据上述要求，自己总结规则、描述算法并给出测试案例
2）可使用任何语言；如果使用C/C++，函数原型如下：
bool match(const char *source[], const char *input)，其中：
source是姓名所含各字的拼音。
示例如下：假设source={"wang","hai","bao",null}，则
match(source,"whb")=true;
match(source,"whba")=true;
match(source,"wanhb")=false;
题目描述的使用场景很常见，在通讯录输入汉字的拼音或者拼音的首字母，查找相匹配的联系人姓名。
中文联系人姓名一般都是由多个汉字组成，只要做到每个汉字的拼音都被顺序匹配，那么这个联系人就和拼音匹配的。所以我们可以将多个汉语拼音的顺序匹配分解为 单个汉语拼音的匹配的与运算（&）。
#include <iostream>
#include <string>
#include <algorithm>
#import <mach/mach_time.h>
using namespace std;
/**
匹配 递归调用,相当于每次都是新的状态
@param source 每次source+1
@param input input指针前移
@param len 长度减去已经匹配的长度
@return 是否匹配
*/
bool match(const char *source[], const char *input, long len){
if (source == NULL || *source == NULL) {
return false;
}
if (input == NULL || len <= 0) {
return false;
}
const char** p_src = source;
char in_f_c = input[0];
char src_f_c = p_src[0][0];
const char* word = p_src[0];
long word_len = strlen(word);
if (in_f_c == src_f_c) {
//input只有一个字符
if (len == 1) {
return true;
}
//汉字的拼音只有一个字符
if (word_len == 1) {
if (word_len == len) {//如果input也只有一个匹配
return true;
}
//这次匹配完成 跳到下一个汉字匹配状态
return match(p_src+1, input+1, len - 1);
}
//最后一个汉字的拼音，支持头匹配
if (*(source + 1) == NULL) {
//如果input的长度大于最后一个汉字的长度，不匹配
if (word_len < len) {
return false;
}
//判断 input剩余的串是否和最后一个汉字头匹配
if (strncmp(word + 1, input + 1, len - 1) == 0) {
return true;
}
}else{
//判断拼音首字母之外的字母是否匹配
if (strncmp(word + 1, input + 1, word_len - 1) == 0) {//匹配
//如果拼音的长度和input的长度一样，匹配成功
if (word_len == len) {
return true;
}
//进入下个汉字拼音匹配状态， input增加word_len长度
bool ret = match(p_src + 1, input + word_len, len - word_len);
if (!ret) {
return match(p_src + 1, input + 1, len - 1);
}else {
return ret;
}
}else {
//进入下个汉字拼音匹配状态， input增加1
return match(p_src + 1, input + 1, len - 1);
}
}
}
return false;
}
bool match(const char *source[], const char *input){
string str = string(input);
transform(str.begin(), str.end(), str.begin(), (int (*)(int))tolower);
return match(source, str.c_str(), str.length());
}
int main(int argc, const char * argv[]) {
//特殊用例测试
const char* source1[] = {"wan", "an", "gang", NULL};
cout<< match(source1, "wang")<<endl;
//题目测试用例
const char* source[] = {"wang", "hai", "bao", NULL};
cout<< match(source, "whb")<<endl; //match(source,"whb")=true;
cout<< match(source, "whba")<<endl; //match(source,"whba")=true;
cout<< match(source, "WHBo")<<endl; //match(source,"wanhb")=false;
return 0;
}
