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

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本