题目: 给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1: 输入: “()” 输出: true 示例 2: 输入: “()[]{}” 输出: true 示例 3: 输入: “(]” 输出: false 示例 4: 输入: “([)]” 输出: false 示例 5: 输入: “{[]}” 输出: true
思路: 刚看到题目也有一种先入后出来加减括号的想法,但奈何不会栈。。。无从下手。 所以自己摸索出来另一种方法。 先定义一个整数数组,初始化为零。然后遇到左括号就往数组里存一个对应得ASCII码,如果是右括号就让数组指针往前然后减一个对应得ASCII码(要加右括号与左括号ASCII的差值是其为0)。例如:“()”遇到’(‘就让数组a[0]+=(,(就是把’('的ASCII (40) 存入了啊[0])遇到‘)'就让a[0]=a[0]-)+1(因为‘)’ASCII码为41,所以加了1)。 注:各括号的ASCII码分别是(=40,)=41, [=91, ]=93, {=123, }=125.
代码:
bool isValid(char * s){ if(strlen(s)==1) return false; int j=0,i,max=0; int a[10000]={0}; for(i=0;i<strlen(s);i++) { if(*(s+i)=='('||*(s+i)=='{'||*(s+i)=='[') { a[j]+=s[i]; j++;} if(*(s+i)==')') { j--; if(j<0) return false; a[j]=a[j]-s[i]+1; } if(*(s+i)=='}'||*(s+i)==']') { j--; if(j<0) return false; a[j]=a[j]-s[i]+2; } if(j>max) max=j; } for(i=0;i<max;i++) { if(a[i]!=0) return false; } return true; }