网站建设的好处和目的,大坪网站建设,个人网站相册怎么做,企业网站建设 论文字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk#xff1a;
每一对相邻的单词只差一个字母。 对于 1 i k 时#xff0c;每个 si 都在 wordList 中。注意#xff0c; begi…字典 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 100000int 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;elsereturn 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; //初始起始字符串入队列尾指针1int 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函数进行判断。最后返回最短转换序列数
总结
本题考察广度优先搜索的引用由于判断最后一位的过程和队列的特点比较符合故采用队列记录字符串经判断后输出最短转换序列数。
