网站后台维护一般要怎么做,wordpress什么叫通配符,网站建设一般怎么付款,南京中如建设公司按字典 wordList 完成从单词 beginWord 到单词 endWord 转化#xff0c;一个表示此过程的 转换序列 是形式上像 beginWord - s1 - s2 - ... - sk 这样的单词序列#xff0c;并满足#xff1a;
每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 s…按字典 wordList 完成从单词 beginWord 到单词 endWord 转化一个表示此过程的 转换序列 是形式上像 beginWord - s1 - s2 - ... - sk 这样的单词序列并满足
每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 si1 i k必须是字典 wordList 中的单词。注意beginWord 不必是字典 wordList 中的单词。sk endWord
给你两个单词 beginWord 和 endWord 以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 如果不存在这样的转换序列返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
思路一BFS
char** list;
int** back;
int* backSize;void dfs(char*** res, int* rSize, int** rCsize, int* ans, int last, int retLevel){int i ans[last];if(i 0){res[*rSize] (char**)malloc(sizeof(char*) * retLevel);(*rCsize)[*rSize] retLevel;for(int j 0; j retLevel; j){res[*rSize][j] list[ans[j]];}(*rSize);}if(last 0){return;}for(int j 0; j backSize[i]; j){int k back[i][j];ans[last-1] k;dfs(res,rSize,rCsize,ans,last-1,retLevel);}
}char *** findLadders(char * beginWord, char * endWord, char ** wordList, int wordListSize, int* returnSize, int** returnColumnSizes){*returnSize 0;int size wordListSize1;int wlen strlen(beginWord);list (char**)malloc(sizeof(char*)*size); back (int**)malloc(sizeof(int*) * size); backSize (int*)malloc(sizeof(int) * size);int* visited (int*)malloc(sizeof(int) * size); int** diff (int**)malloc(sizeof(int*) * size); int* diffSize (int*)malloc(sizeof(int) * size);int endidx 0;for (int i 0; i size; i) {list[i] i 0 ? beginWord : wordList[i - 1];visited[i] 0;diff[i] (int*)malloc(sizeof(int) * size);diffSize[i] 0;back[i] (int*)malloc(sizeof(int) * size);backSize[i] 0;if (strcmp(endWord, list[i]) 0) {endidx i;}}if (endidx 0) return 0; // endword is not in the list// collect diff datafor (int i 0; i size; i) {for (int j i; j size; j) {int tmp 0; // tmp is the difference between word[i] word[j]for (int k 0; k wlen; k) {tmp list[i][k] ! list[j][k];if (tmp 1) break;}if (tmp 1) {diff[i][diffSize[i]] j;diff[j][diffSize[j]] i;}}}// BFSint* curr (int*)malloc(sizeof(int) * size); int* prev (int*)malloc(sizeof(int) * size); int prevSize, currSize 1;int* currvisited (int*)malloc(sizeof(int) * size);int level 1; curr[0] 0;visited[0] 1;int retlevel 0; while (retlevel 0 currSize 0) {level;int* tmp prev;prev curr;curr tmp;prevSize currSize;currSize 0;for (int i 0; i size; i) {currvisited[i] 0;}for (int i 0; i prevSize; i) {for (int j 0; j diffSize[prev[i]]; j) {int k diff[prev[i]][j]; if (visited[k]) continue;back[k][backSize[k]] prev[i]; if (k endidx) retlevel level; if (currvisited[k]) continue; curr[currSize] k;currvisited[k] 1;}}for (int i 0; i currSize; i) {visited[curr[i]] 1;}}if (retlevel 0) return 0; char*** res (char***)malloc(sizeof(char**) * size);int* ans (int*)malloc(sizeof(int) * retlevel);*returnColumnSizes (int*)malloc(sizeof(int) * size);ans[retlevel - 1] endidx;dfs(res, returnSize, returnColumnSizes, ans, retlevel - 1, retlevel);return res;
}
分析
本题采用广度优先搜索将每个字符串能转换的所有序列找出再判断是否存在最短转换序列最后输出答案
总结
本题考察广度优先搜索的应用判断当前字符是否匹配得到转换序列即可做出
