leetcode做题笔记127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

 思路一：BFS

#define MAX_QUEUE_LEN 100000
 
int isSequ(char* a, char* b){
    int len = strlen(a);
    int count = 0;
    for(int i = 0; i < len; i++){
        if(a[i] != b[i])
            count++;
    }
    if(count == 1)
        return true;
    else
        return false;
 
}
 
int ladderLength(char *beginWord, char *endWord, char **wordList, int wordListSize)
{
    char* queueList[MAX_QUEUE_LEN] = {0};       //定义一个很大的数组，用来当做队列
    int head = 0;                               //需要首尾指针标记
    int tail = 0; 
 
    for(int i = 0; i < wordListSize; i++){
        if(strcmp(endWord, wordList[i]) == 0){  //字符串中有可以匹配的
            break;
        }
        if(i == wordListSize-1) return 0;       //字符串数组中没有匹配的，return 0
    }
    int* mark = (int*)malloc(wordListSize*sizeof(int)); //需要标识这个字符串是否已经遍历过了，避免死循环
    memset(mark, 0, wordListSize * sizeof(int));
 
    queueList[tail++] = beginWord;              //初始，起始字符串入队列，尾指针+1
    int step = 1;
    while(head != tail){                        //队列不为空，遍历未结束
        int scop = tail-head;                   //广度搜索，当前这一层有多少个
        for(int i = 0; i < scop; i++){      
            char *temp = queueList[head++]; 
            if(strcmp(temp, endWord) == 0){     //相当于出队列，判断是否符合。首指针++
                free(mark);         
                return step;
            }
            for(int j = 0; j < wordListSize; j++){  //相当于搜索下一层，查是否存在可以变化的  
                if(mark[j] == 0 && isSequ(temp, wordList[j])){
                    mark[j] = 1;
                    queueList[tail++] = wordList[j];
                }
            }
        }
        step++;
    }
    free(mark);
    return 0;
}

分析：

本题要将返回最短转换序列的数目，可以采用广度优先搜索和队列解决问题，将字符存入队列，不断判断队列中结尾字符是否符合，不断使用isSequ函数进行判断。最后返回最短转换序列数

总结：

本题考察广度优先搜索的引用，由于判断最后一位的过程和队列的特点比较符合，故采用队列记录字符串经判断后输出最短转换序列数。