算法之有效的括号

题目

1 英文：

  Given a string containing just the characters '(', ')', '{', '}', '[' 
  and ']', determine if the input string is valid.
  An input string is valid if:  
  1.Open brackets must be closed by the same type of brackets.
  2.Open brackets must be closed in the correct order.

2.中文

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

3. for example

   输入: "()"
   

   输出: true 示例 2:

   输入: "()[]{}" 输出: true 示例 3:

   输入: "(]" 输出: false 示例 4:

   输入: "([)]" 输出: false 示例 5:

   输入: "{[]}" 输出: true

思路

对自己要求

1. 只能接受线性时间复杂度算法
2. 空间复杂尽量小，代码尽量简洁

思路一

1. 之前从算法基础一本书看过，关于 "(" ")" 组成有效括号

2. for example:

   "(     (     (    (    )   (      )       )     )     )  "
    1     2     3    4   -4   4      -4      -3   -2    -1=0 是个有效括号
   

3. 套到这题上面，有3个情况 假设用 3个数做基数 "(" 从1 开始 '[' 从100 开始 "{" 从1000开始

   "{                (            [             ]               )              }"
    1001             2          103           -103            -2            -1001  =0
   

4. 缺点：可能存在100小括号，加统计，如果超过100 小括号，需要进位，但是，就算可以进位，之前的计算结果怎么处理？所以这个想法只能验证局部

思路二

1. 遍历字符串 如果碰到左括号拼接字符串，如果碰到右括号的，查看拼接字符串长度 ，遍历后面等长，并且将')' 转换成'('并拼接 ，完成后和左括号的字符串比较
2. 代码实现：

 def isValid( ss):
        """
        :type s: str
        :rtype: bool
       """
        if len(ss)%2!=0:
            return False
        temp={')':'(',']':'[','}':'{'}    
        index=0#遍历下标，两种情况会加 如果都是 左括号 则 +1 如果是右括号 也要+1 固定量的 1
        su=""
        while index<len(ss):
            s=ss[index]
            if s in temp:#是否是 右括号  存在右括号
                #遍历指定长度，后拼接另外字符串和su比较 如果不等 则返回false
                ne=len(su)
                end=''
                print(end)
                if ne==0:
                    return False
                while ne>0:
                    s=ss[index]
                    if s not in temp:
                    #假设拿到　没有对应的匹配关系，则肯定不满足需求
                        return False
                    end=temp[s]+end
                    ne-=1
                    index+=1
                    if index>=len(ss):
                        if end !=su:
                            return False
                else:
                    if end !=su:
                        return False
                    else:
                        su=''#如果相等　则清零ｓｕ，用于下次在比较
            else:#如果是左括号则 拼接字符串
                su+=s
                index+=1
        return not su

1. 多次测试发现自己想法有问题： "(([]){})" 这样的字符串，是有效的，但是我的程序，会解析成 无效

学习别人思路

1. 其实这个是递归问题，可以用递归处理，但是递归效率太低，另外一个方式用广度或者深度枚举，这里觉得 深度比较符合场景（这里不得不批评下自己，学习那么多，广度和深度，这里一直卡在一种思路上面，而且这个思路，还是错误的场景），通过压栈的方式

2. show code:

       def isValid(self, ss):
           """
           :type s: str
           :rtype: bool
          """  
           temp={')':'(',']':'[','}':'{'}    
           l=list()
           for i in ss:
               if i not in temp:#如果是左括号 则压栈
                   l.append(i)
               else:
                   if l==[] or temp[i]!=l.pop():
                      #如果栈顶没数据 则有个单的 右括号   
                      #如果出栈和当前')' 获取到'(' 不相等则 也不是封闭的
                       return False
           return  l==[]
   

3. 总结：

   1. 其实自己的想法 就是类似手动实现 压栈的操作，但是没有完整栈操作合理
   2. 一个点想不通的，立马换个思路，实践大于理论