链接：https://leetcode.cn/problems/remove-invalid-parentheses/solution/by-xun-ge-v-e70k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
题意删除最小的括号，使字符串有效->有效的括号->有效的括号最多
首先需要实现给定任意字符串，判断字符串是否有效
然后遍历字符串，每次删除一个字符，判断删除后的字符串是否有效

具体实现
给定字符串判断字符串是否有效，不必多说，不会的看一下本站32题，基本思路都是栈模拟判断

遍历整个字符串，对字符串进行删除操作，可以是回溯+剪枝实现，也可以BFS+哈希实现。这里选择BFs+哈希
遍历整个字符串，用队列保存删除后的字符串，将字符串按每一层的每一个位进行删除，删除后判断是否为有效字符串，有效则保存，同时设置标志位记录是否有一层存在有效字符串，存在则可以不需要遍历了，因为上面一层永远比下面一层大，无效则舍弃，因为字符串按位删除会操作相同情况，同时删除和的有效字符串与会存在相同，所以可以利用哈希进行去重，对哈希算法不熟悉的可以看链接哈希算法详解
广度优先搜索过程可以类比与树的层次遍历

不清楚的看代码，代码注释超级详细

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


struct my_struct {//哈希结构，以字符串为键
    char name[25];
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};
 
struct my_struct *users = NULL;//有效字符串哈希表
struct my_struct *users_str = NULL;//删除后字符串哈希表

bool ifBrackets(char * str)//判断字符串是否有效
{
    int conut = 0;
    int len = strlen(str);
    if(len == 0)
    {
        return false;
    }
    for(int i = 0; i < len; i++)
    {
        if(str[i] == '(')
        {
            conut++;
        }
        if(str[i] == ')')
        {
            conut--;
        }
        if(conut < 0)
        {
            return false;
        }
    }
    if(conut == 0)
    {
        return true;
    }
    return false;
}

char ** removeInvalidParentheses(char * s, int* returnSize){
    char ** ans = malloc(sizeof(char *) * 250);//返回值列表
    *returnSize = 0;
    char res[35000][25];//队列，保存删除后字符串
    int left = 0;
    int right = 0;
    strcpy(res[right++], s);//入队
    bool logo = true;//标志位，当 当前层存在有效字符串时，下面一层就不需要再删除了
    while(left < right && logo == true)//遍历整个队列
    {
        
        int r = right;
        while(left < r)//判断当前层字符串
        {
            int len = strlen(res[left]);
            if(ifBrackets(res[left]) == true)//有效字符串
            {

                struct my_struct *s;//哈希去重
                HASH_FIND_STR(users, res[left], s);
                if(!s)
                {
                    s = (struct my_struct *)malloc(sizeof(struct my_struct));
                    strcpy(s->name, res[left]);
                    s->id = 1;
                    HASH_ADD_STR(users, name, s);  /* id: name of key field */
                    ans[(*returnSize)] = malloc(sizeof(char) * (len+1));
                    strcpy(ans[(*returnSize)], res[left]);
                    (*returnSize)++;
                }

                logo = false;//存在有效字符，不需要再删除了
            }

            for(int i = 0; i < len && logo == true; i++)//将本层的所有字符串按位删除
            {
                if(res[left][i] != '(' && res[left][i] != ')')//是字母不需要删除
                {
                    continue;
                }

                int r = 0;//删除对应位
                for(int j = 0; j < len; j++)
                {
                    if(j == i)
                        continue;
                    res[right][r++] = res[left][j];
                }
                res[right][r] = '\0';

                struct my_struct *s;//删除后的字符串去重
                HASH_FIND_STR(users_str, res[right], s);
                if(!s)
                {
                    s = (struct my_struct *)malloc(sizeof(struct my_struct));
                    strcpy(s->name, res[right]);
                    s->id = 1;
                    HASH_ADD_STR(users_str, name, s);  /* id: name of key field */
                    right++;
                }

            }
            left++;
        }
    }
    //销毁哈希表
    struct my_struct *current_user, *tmp;
    HASH_ITER(hh, users, current_user, tmp) {
        HASH_DEL(users, current_user);  /* delete; users advances to next */
        free(current_user);             /* optional- if you want to free  */
    }
    HASH_ITER(hh, users_str, current_user, tmp) {
        HASH_DEL(users_str, current_user);  /* delete; users advances to next */
        free(current_user);             /* optional- if you want to free  */
    }
    if(*returnSize == 0)
        ans[(*returnSize)++] = "";
    return ans;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/remove-invalid-parentheses/solution/by-xun-ge-v-e70k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。