C语言 | Leetcode C语言题解之第126题单词接龙II

2024-06-02 10:20

本文主要是介绍C语言 | Leetcode C语言题解之第126题单词接龙II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

题解:

char** list;
int** back;
int* backSize;// DFS uses backtrack information to construct results
void dfs(char*** res, int* rSize, int** rCSizes, int* ans, int last, int retlevel) {int i = ans[last];if (i == 0) {res[*rSize] = (char**)malloc(sizeof(char*) * retlevel);(*rCSizes)[*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, rCSizes, ans, last - 1, retlevel);}
}char*** findLadders(char* beginWord, char* endWord, char** wordList, int wordListSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int size = wordListSize + 1;  // new sizeint wlen = strlen(beginWord);list = (char**)malloc(sizeof(char*) * size);  // new wordlistback = (int**)malloc(sizeof(int*) * size);    // data to backtrack indexes while BFSbackSize = (int*)malloc(sizeof(int) * size);int* visited = (int*)malloc(sizeof(int) * size);  // visited flag in BFSint** diff = (int**)malloc(sizeof(int*) * size);  // list diff[i] are indexes which can connect to word[i]int* diffSize = (int*)malloc(sizeof(int) * size);int endidx = 0;// Intialization 1for (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);  // curr level in BFSint* prev = (int*)malloc(sizeof(int) * size);  // prev level in BFSint prevSize, currSize = 1;int* currvisited = (int*)malloc(sizeof(int) * size);  // to make sure curr members are uniqueint level = 1;                                        // level of laddercurr[0] = 0;visited[0] = 1;int retlevel = 0;  // ladder size, marks the end of BFSwhile (retlevel == 0 && currSize > 0) {++level;// switch prev and currint* tmp = prev;prev = curr;curr = tmp;prevSize = currSize;currSize = 0;// reset currvisited for each level currfor (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];  // k is the candidate of curr (next level of BFS)if (visited[k]) continue;back[k][backSize[k]++] = prev[i];   // backtrackif (k == endidx) retlevel = level;  // find the lowest ladder level, finish current BFSif (currvisited[k]) continue;       // no duplicates in curr listcurr[currSize++] = k;currvisited[k] = 1;}}// set visited after search through one level, different from Q127for (int i = 0; i < currSize; ++i) {visited[curr[i]] = 1;}}if (retlevel == 0) return 0;  // no ladder found// DFS to construct resultchar*** 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;
}

这篇关于C语言 | Leetcode C语言题解之第126题单词接龙II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1023691

相关文章

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Go语言中Recover机制的使用

《Go语言中Recover机制的使用》Go语言的recover机制通过defer函数捕获panic,实现异常恢复与程序稳定性,具有一定的参考价值,感兴趣的可以了解一下... 目录引言Recover 的基本概念基本代码示例简单的 Recover 示例嵌套函数中的 Recover项目场景中的应用Web 服务器中

Go语言中使用JWT进行身份验证的几种方式

《Go语言中使用JWT进行身份验证的几种方式》本文主要介绍了Go语言中使用JWT进行身份验证的几种方式,包括dgrijalva/jwt-go、golang-jwt/jwt、lestrrat-go/jw... 目录简介1. github.com/dgrijalva/jwt-go安装:使用示例:解释:2. gi

Go 语言中的 Struct Tag 的用法详解

《Go语言中的StructTag的用法详解》在Go语言中,结构体字段标签(StructTag)是一种用于给字段添加元信息(metadata)的机制,常用于序列化(如JSON、XML)、ORM映... 目录一、结构体标签的基本语法二、json:"token"的具体含义三、常见的标签格式变体四、使用示例五、使用