背景：LeetCode - 127. Word Ladder
解决：
简单的广搜，用C++真的太好实现了，STL确实强大，但是用C语言来写呢？其实关键点就在于字符串如何判重，STL里的set可以搞，但是注意C里面没有这个东西，所以要么我们自己手写一个红黑树来实现set(红黑树不好写！很麻烦)，要么就使用字典树(这个确实相对来说好些得多)。写这个题其实也是自己想多学学C语言中一些高级的东西，所以就用Linux内核的代码风格来实现了下，不得不说相比较自己以前写的代码确实华丽多了,还有一点，我觉得很必要，就是内存的回收，虽然这个题我写了内存回收时间还长了，但是我个人觉得这是必要的，养成好习惯嘛。
代码：
typedef struct tagNode Node; typedef Node * pNode; typedef struct tagQueue Queue; typedef Queue *pQueue; typedef struct tagUsed Used; typedef Used *pUsed; typedef struct tagDicTree DicTree; typedef DicTree *pDicTree; typedef char *String; struct tagNode { String string; int step; }; struct tagQueue { pNode val; pQueue next; }; struct tagDicTree { pDicTree alp[26]; int exsit; }; struct tagUsed { pDicTree root; int (*search)(pDicTree root, const char *str, int len); void (*insert)(pDicTree root, const char *str, int len); void (*free_space)(pDicTree root); }; #define INIT_STRUCT_USED(pused) (pused) = (pUsed)malloc(sizeof(Used)); \ (pused)->root = (pDicTree)malloc(sizeof(DicTree)); \ memset((pused)->root, 0, sizeof(DicTree)); \ (pused)->search = search; \ (pused)->insert = insert; \ (pused)->free_space = free_space; int search(pDicTree root, const char *str, int len) { int i = 0; pDicTree p = root; for (; i < len; i++) { int index = str[i] - 'a'; if (p->alp[index] != NULL) p = p->alp[index]; else break; } return i!= len ? 0 : (p->exsit == 1); } void insert(pDicTree root, const char *str, int len) { int i = 0; pDicTree p = root; for (; i < len; i++) { int index = str[i] - 'a'; if (p->alp[index] == NULL) { p->alp[index] = (pDicTree)malloc(sizeof(DicTree)); memset(p->alp[index], 0, sizeof(DicTree)); p->exsit = 0; } p = p->alp[index]; } p->exsit = 1; } void free_space(pDicTree root) { int i; if (root == NULL) return ; for (i = 0; i < 26; i++) free_space(root->alp[i]); free(root); } int check_bit_one(const char *str1, const char *str2, int len) { int ret = 0, i; for (i = 0; i < len; i++) if (str1[i] != str2[i]) ++ret; return ret == 1; } int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) { int len = strlen(beginWord); int i; pUsed used = NULL; pQueue head = (pQueue)malloc(sizeof(Queue)), tail = head; head->val = (pNode)malloc(sizeof(Node)); head->val->string = beginWord; head->val->step = 1; head->next = NULL; INIT_STRUCT_USED(used); while (head != NULL) { pNode pre = head->val; pQueue tQ = head; if (!strcmp(pre->string, endWord)) return pre->step; for (i = 0; i < wordListSize; i++) { if (check_bit_one(pre->string, wordList[i], len) && !used->search(used->root, wordList[i], len)) { tail->next = (pQueue)malloc(sizeof(Queue)); tail = tail->next; tail->next = NULL; tail->val = (pNode)malloc(sizeof(Node)); tail->val->string = wordList[i]; tail->val->step = pre->step + 1; used->insert(used->root, wordList[i], len); } } head = head->next; free(tQ); } used->free_space(used->root); return 0; }