作者:Guang
链接:https://leetcode.cn/problems/brace-expansion-ii/solutions/997719/xss1096-hua-gua-hao-zhan-kai-iiby-zgh-by-vumf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
从题目来看,有几个要注意:
题目提出“返回它所表示的所有字符串组成的有序列表”,因此结果要按字母排序后返回。
示例中提到:不应出现重复的组合结果。表明需要去重,则最好使用hash。
代码中使用了递归DFS,每次处理首先遇到的最内层的括号(即括号内不含子括号),split按逗号拆分,按每个拆分元素与剩余部分组合成新字符串DFS。 直到一条处理路径中新字符串不含子括号为止,用逗号切分,添加到hash表。 全部路径处理完后,排序hash表。返回结果。
举个例子: 输入:{a,b},x{c,{d,e}y}
从左到右处理第一个括号内不含子括号的内容 括号内容:a,b 按逗号切分为a和b 分别取a和b与其余部分组合。以a为例,a,x{c,{d,e}y}作为新字符串。继续处理。
输入a,x{c,{d,e}y}从左到右取括号内不含子括号的部分 括号内容:d,e 按逗号切分为d和e 继续与其余部分组合,以d为例:a,x{c,dy}
输入: a,x{c,dy} 括号内容:c,dy 按逗号切分:c和dy 与其余部分组合:以c为例为a,xc 以dy为例为a,xdy
输入:a,xc和a,xdy 无括号,则拆分后插入哈希表。此轮插入了a,xc,xdy
回到上面第2步的结果,取e继续:a,x{c,ey} 继续拆分下来,第一部分a,xc第二部分a,xey.插入哈希表a,xc,xey
回到上面第一步的结果,取b的组合结果处理b,x{c,{d,e}y} 拆分一次,分为b,x{c,dy}和b,x{c,ey},继续拆分,插入哈希表:b,xc,xdy,b,xc,xey
哈希表中保存的a,xc,xdy,xey,b 使用HASH_SORT排序,结果a,b,xc,xdy,xey。遍历哈希表,结果输出到二维数组。
代码
#define SIZE 62
typedef struct {//哈希结构
char str[62];
UT_hash_handle hh;
} HashNode;
HashNode *g_hashMap = NULL;
void hashAdd(HashNode **map, char *name)//加入哈希表
{
HashNode *node = NULL;
HASH_FIND_STR(*map, name, node);//查询是否在哈希表中存在
if (node == NULL) {
node = (HashNode *)malloc(sizeof(HashNode));//不存在加入哈希表
strcpy(node->str, name);
HASH_ADD_STR(*map, str, node);
return;
}
strcpy(node->str, name);
}
HashNode *hashFind(HashNode *map, char *name)//查询是否在哈希表中
{
HashNode *node = NULL;
HASH_FIND_STR(map, name, node);
return node;
}
static inline int IsExistLeftBacket(char* expression)//查找{
{
while (*expression) {
if (*expression == '{') {
return true;
}
++expression;
}
return false;
}
static inline int Split(char* str, char* splitStr, char (*ret)[SIZE])//字符串切割
{
char *q = strtok(str, splitStr);
int count = 0;
while(q) {
strcpy(ret[count], q);
++count;
q = strtok(NULL, ",");
}
return count;//返回切割点
}
void Dfs(char* expression)
{
if (expression == NULL) {
return ;
}
if (!IsExistLeftBacket(expression)) {//如果没有 { 号,说明不需要再递归
char split[SIZE][SIZE] = {0};//结束入口
int strCnt = Split(expression, ",", split);
for (int i = 0; i < strCnt; i++) {
hashAdd(&g_hashMap, split[i]);//有效数据加入哈希表
}
return;
}
char leftCash[SIZE] = {0};
char rightCash[SIZE] = {0};
char middleCash[SIZE] = {0};//临时存储区
int left, right, i;
int len = strlen(expression);
for (i = 0; i < len && expression[i] != '}'; ++i) {//寻找第一个{ ,为后序递归准备
if (expression[i] == '{') {
left = i;
}
}
right = i;
strncpy(leftCash, expression, left);
leftCash[left] = '\0';
strcpy(rightCash, expression + right + 1);
strncpy(middleCash, expression + left + 1, right - left - 1);
middleCash[right - left - 1] = '\0';//临时区处理
char split[SIZE][SIZE];
int splitCount = Split(middleCash, ",", split);
for (i = 0; i < splitCount; ++i) {//遍历并递归到下一层
char cache[SIZE];
memset(cache, 0, sizeof(cache));
strcpy(cache, leftCash);
strcat(cache, split[i]);
strcat(cache, rightCash);
Dfs(cache);
}
}
int Cmp(const HashNode *a, const HashNode *b)//字典序排序
{
return strcmp(a->str, b->str);
}
char ** braceExpansionII(char * expression, int* returnSize)
{
if (expression == NULL) {
*returnSize = 0;
return NULL;
}
g_hashMap = NULL;
Dfs(expression);//头递归
*returnSize = HASH_COUNT(g_hashMap);//获取哈希表中数据个数
HASH_SORT(g_hashMap, Cmp);//排序
char** ret = (char**)malloc(sizeof(char*) * (*returnSize));
HashNode *tmp = NULL;
int index = 0;
for (tmp = g_hashMap; tmp != NULL; tmp = tmp->hh.next) {//枚举哈希表所有数据并保存
ret[index] = (char*)malloc(sizeof(char) * SIZE);
strcpy(ret[index], tmp->str);
index++;
}
return ret;
}