leetcode做题笔记126. 单词接龙 II

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= 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 = wordListSize+1;
    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 data
    for (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;
            }
        }
    }
    // BFS
    int* 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;
}

分析：

本题采用广度优先搜索将每个字符串能转换的所有序列找出，再判断是否存在最短转换序列，最后输出答案

总结：

本题考察广度优先搜索的应用，判断当前字符是否匹配，得到转换序列即可做出