刷爆leetcode第六期 0017

编号0017

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses

我们假设字符串有这些符号组成

当我们遍历到左括号的时候 我们就对其进行压栈操作

c语言代码表示如下

typedef char StackType;

typedef struct Stack
{
	StackType* a;  //储存数据的大小
	int Top;       //栈顶
	int Capacity;  //数组容量大小 
}ST;

void StackInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->Top = 0;
	p->Capacity = 0;
}

StackType StackTop (ST* p)
{
	assert(p);
	return p->a[p->Top - 1];
}

void StackPush(ST* p, StackType x)
{
	assert(p);
	if (p->Top==p->Capacity)
	{
		int NewCapacity = p->Capacity == 0 ? 4: p->Capacity * 2;
		StackType* Tmp = realloc(p->a,NewCapacity*sizeof(StackType));
		if (Tmp==NULL)
		{
			perror("StackPush realloc");
		}
		else
		{
		    p->Capacity = NewCapacity;
			p->a = Tmp;
		}
	}

	p->a[p->Top] = x;
	p->Top++;
}

void StackPop(ST* p)
{
	assert(p);
	assert(p->Top > 0);

	p->Top--;
}

void StackPrint(ST* p)
{
	assert(p);
	while (p->Top>0)
	{
		printf("%d  ", p->a[p->Top - 1]);
		StackPop(p);
	}
}

int StackSize(ST* p)
{
	assert(p);
	return p->Top;
}


bool StackEmpty(ST* p)
{
	assert(p);
	return p->Top==0;
}

void StackDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->a == NULL;
	p->Capacity = 0;
	p->Top = 0;
}

ST st1;

bool isValid(char * s)
{
    StackInit(&st1);
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st1,*s);
            s++;
        }
        else
        {
            StackType top = StackTop(&st1);
            StackPop(&st1);
            if((*s==')'&& top!='(')
            || (*s==']'&& top!='[')
            || (*s=='}'&& top!='{')
            )
            {
                StackDestroy(&st1);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    StackDestroy(&st1);
    return true;
}

我们提交试试看

咦 我们可以发现 这里好像没有匹配成功过 直接遍历完了也返回true了

那么这里我们可以判断下是否为空 如果为空我们返回假就好了

我们再测试下看看

咦 有出错了

我们发现 这里栈上还没有数据 直接就开始出栈了 当然就报错了

那么我们再打个补丁

            // 如果遇到了后面的括号 且栈为空 直接return false
            if(StackEmpty(&st1))
            {
                return false;
            }

之后我们再试试看

成功通过所有测试用例