【LeetCode】20. Valid Parentheses

时间:2022-05-26 15:52:43

题目:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAvcAAABJCAIAAAA2Qp7AAAAQY0lEQVR4nO2dO3byPBCG/82wAtYRFsAeviIroE+bDbjKCrIBV5Qp0uScVO5oA4EkhwP8BRfrMiONLAls8T6HIoCtuWgkvZYh/HcAAAAAACiR/27tAAAAAABAFqByAAAAAFAmUDkAAAAAKBOoHAAAAACUCVQOAAAAAMoEKgeAXOx3++3m92+1/lt+Rz1W6+3mZ7/bwVyp5lIxULcByAdUDgBZ2O/2CRYbfeHZ7/cwV565VAzUbQCyApUDQBa2m9+U683y+2/5vd38wlx55lIxULcByEohKqdpmlu74GcQTjrg/B96XBfSBpL4qvr4WK1hrjxzqRiE28OdLnrreZBjvY0iH7TKqWdjhWnVqO+oT/tAU005n/rjrcPJC15vk4TTrRHOf/X1ejYez+pI91SSN+hA0kFhpF9vlt9/y2+YK89cF6jBcWO3/eM1/ShLPyueFz+90VQTXfIlKSiludfKTAvupVmmfV+H2Cqnno31U6wXekaOkZOcQTjpAConGGLBeH95G00+XomFZPGov84fGWXu/eXt4eUrxLH46BaPk/loMn+sc5v7ev5nGsob3WfzMJmPJnM7yYHmuiBUObYzr09Hn+dGJcS7fRuVkxgmiKwTXQypVE6f8YmnUJVDHq/k5mTPOEx52lRTew+ono2nVX15h/FYOZXTVVbryguz+nBoqum0qmbnA3QNSDtw2bc6nkiZvRjRHJdHajjJRer1Nkk4aiPK264utPy3MzCrT01UpFdkrrxJ5hukE2j0Pl9Rpi07QNJhs313VNRlcf1BLSRfz/+stZk+MmxhphpZPFI6IJu5v/eXt9HT4mrmlvXH6F/zfh1zn82DbSvEnGMe6DS65SVH6d3gLDldsgdHp1FWV9Px5el4PKtbg6dGJLOid/5R1jVrtkg60ckm+fb1ixvkdM3NzKQrV1grWzniTgSrHyQrY5sotzMthsoR3zTR3Lw80aSiro20qvQGTu8fqYfoiTm311RTS3OcV3TKAeXPU37JnrOja6qp7osnUvZSQIlU4m2ScJwqx59kFTMuX+xcQ2SSXWFSCbR7n8sz3aHU3+oTvX06US3MkmOti6wOIFfQ0IWZXPKFL6Yw9/pk7hnkjc7aFctozqFyJOZc9SmZQ7qXHKtywrLEu+QaQWGj7DiP2YlpT/DOisL5h5pc/JF2NuSa3HQZaMxaB/2Zb0JlD860VlrygEworR8kK2Or2NxjQUVXOU019WzFUWsk7aTaHLtt4LLjSY1mhRw5ohXd3CCQGTUTxaTArxLUY7y7LCnCCVI5esBhd6z8VUEmgX+VKxtJkoMCZB3W2/eVMbXkEI/F4+Tt+VN4cODCTD+oraNs5miVkzE6SuVkMsepnGBzh4MxzAXjSCqsmQd37zLIbc4lyQgSjjLrctL6O3RCIxe5YJUTbcgxyQtyGqRy6CgyrJWkyqGh9AN7iKVyBGNBxalytO0jc8vITr++26SeJlc5R13G7MEpFgwv1Z7To3f1HKtVDJN2EdXGntflKHkt2pHGqhxJOAIr3iRz6eG9oqvCl2RP2dgJ5KYV7TDGVvsy7zA7PMhqlq037AV0Ph3A7B7lMff6JFdUSaILUo1x5pKoHHIeYMaReW/kxiqHc8k9gsJGmWZDnXalKkcy/yRROYGGvJO8YTf0+vkGa6XSiGduPOj9px/kXhmnVSMaCyqyO1bE9uDFu7D9CvuZEZu71vQ02JtXg1A5XKQ9UTneJHPpkc3OFIEqh0ug3fvEYSKVQztMDyY9US2y9ab+EAuOVDogSFpFmKs/yM8CZ4/u+DFkUYBx5iJVjmMeGL7K4UdQ2ChLonJ8808ylRNgKLfKUQ681lppr4vc3Ki0oDYkWRkTqBzGeVLlHI+tFAOsNBGoHCM/TpWj+9S95wyjV7pjxUYaq3JE4YhVzqUNK8nkAU6vPF3pEr7eMFmVwx3mK3HeYcdgIvIjFhylqpyz4MBeDmnONQ8IxhFVpQE1cNU7VhfCR1m0yhHNPylUTqAh1yWcP6dilaM7n3mttFSObt0+2NIP/pWRkHzezDPfJDeF0ti+Y9W+o5ekXofiBVV9UbPoOCZWn1JbLK61Vmndul1MjhFO5dCRRqscaTjKpqIajj2a/JdegsHPVoU3yYLZREugpXLYPNMdqlYR5bC7/c57OaXfscLnckhzgvrUD1MHLD26w2ogXuWwLrlGUNgoi1c50vknWuWEGXKpHC2npzaY6VqyD37VtdJSIe5dO7UZ0cpoL16cMy30fwU0bjFSuWiP05tXT7UrknimNq0Y5K/uLa+UZIX2nNrktKqYb5jRNxmVSNuzWENqjzKRxqscSTjmTHE6uNbFhSvJVG5mtdMrsiq8SWYbZBJI7bCRFUV1qB4g6bCjfaJW5aty6KePySsmeQuhnz6OMheuciKjC1U5EeZiP5fDzwPecST/JjnzCFQ5ZJacLtFDPniUJVA5rDN6V3j2mBJNdCKVM5vNqDbo6ZqbmW+xVupp5OdG1RvBjG2rnANXeGShFvILD2ngh/IgocMpLMj+ErDehNy0OhwOh6aaddcBYbtHseY67OVERRe+l9PdXNLvWKVA7knwXg6VJZABTmX1jEEtI/etcrRNRdmnx/qMJJzhRzkU5D8qFLC5slofmBVHaI75r4C5zIVpuHhzQRou1lygyunV71jJVQ6fJZCBvqqcIa+V961yRLdShoQ7HG5vE+Rgu/mRLjniHYjt5ifKXOD3umPNLb//HD+8kNqc3FCi6JhfeAg3lwppDZC/8HA7t4FCX1XOkNfKe1c5AGRiv9sl/o3o1Xq/28FceeZSMVC3AcgKVA4Audjv9tvNb4KFZ7Xebn686w3MDddcKgbqNgD5gMoBAAAAQJlA5QAAAACgTKByAAAAAFAmUDkAAAAAKBOoHAAAAACUCVQOAAAAAMoEKgcAAAAAZQKVAwAAAIAygcoBAAAAQJlA5QAAAACgTKByAAAAAFAmUDkAAAAAKBOoHAAAAACUCVQOAAAAAMoEKgcAAAAAZQKVAwAAAIAygcoBAAAAQJlA5QAAAACgTKByAAAAAFAmUDkAAAAAKBOoHAAAAACUCVQOAAAAAMoEKgeAa7Df7beb37/V+m/5nf6xWm83P/vdroRYhp+fUkENDz3q+wQqB4Ds7Hf7a8ynq/V+vy8klsHmp1RQw0OP+m6BygEgO9vN73Wmy+3mt5hYBpqfUkENDz3qu+WOVE7TNHdoujND9FmlV/5f78JxtS4nlmHmpwzs4YMaHnrUQfRq/oxEUzlNNR1TzOrD4VDPTn90IObcJG021XQ8rW7SbUGm61kuN4NaVn3O0Xe5SdrdKRJwzekyTdRHqNhvvx70Jz/SJB6LMX50+5qiazW0gunhM9Q+Gk4Np4w6ihsul1lg9nKIMKFyutETlRMEVI5CBpXz9fxvPnpaLOuP0eTt+dN4d/E4+Xg9P31/eXt4+Qo5PU3URwQrRGQsf8vP5mEyH03mI+XI16fjK3Pr+MXjZD6azB9rxXr79Nr5kSYxucrh37+Wygnod6o3h1rDZLmShX3bqKO4c5VTXXZ71HeVPSA6N8a5l5prqum0qmbtmfpuUlubl9fb9pXiPb6rPVEPVl6Z1X53j7GfvBqPZ/Whnqmnm+PGckRp2TRtGbKDujyh3WScl3SBMtXWZD9aTc3quH4nY+RONIrBqg1v6Ex3s9Gxpo9ZOh9UzfSKlZxuYl63vT7NR0+L5WfzYE52X8//jDV78Wiu4o7TibmSHlOOMuBizxPL8rN5+Ne8U1e39uLx/vI2elqYR9YfI72FBPkRl58w1YzKMZbg9mlAU57+4qdfch5jh09MvxO9OdQapsuVKuxMUXeoTEei/MtlAYSpHG2dV5KircxEorVzm2qqDWVSuJzOOT67vE7tMSjN8c4of6pGyIscVTOpjrdtMCqHbpnTxVxQSuGqjdmWGRN8F6jrt92PZgrUPMf0uxUjE5pZDMRTyhxrghOwQtNU+K7qcl/7ELPqw8vX8rN5UC8TQ1Zx8nRirnSNKV+3asfkiiVI5ZxsEWuMZjpBfoTlJ0w1v5djnWR/PMDZlL+/+OmXu1qT3bEK63dqvR9kDXPlahd2pqg7ViaXKG4+vOO9HPfSfj7TGmfcFYszm6wJ9W19mWadYVQOGzupgxiHPH5KpkT11cuelvru+WjyLGkXOCUa63NEv7MikgrNTJT+lDMXlHOhaa5aJdXFQCzh1GPxSFzh/XEXx8zD4YYSgqxbBbv90bFkUDkJ8iMrP2mqHXeslKa5qcnRlKC/pAUdqnIC+525Xzm4GmbLVbSDdZvKZBIlnYoHT6zK0TfVuG0zY3hfWme7RN0yc+rTsXX5Tzpj7SU4NuQ0e7WxM+ydHayWafc9Oy7mfKhlzDAR2AVpVI7EKB2jMzQjb94YHXLGtZ/lNG2efH7TXV3uNU82qzKXg0v++lg6V5pjytWtVOw5YwlUOZTaY1fW7vkRlZ841Q6V47hK8jcl6S9++s2hcpz9HrXe96SGneVqD9L0UXeoTF4O8vMhVA5fUjRClXPqUWPTxbMZorTNO8PegSNKorvKIVtOq3IIE4FdkE7l+IwmVjncLahrqhy+uhKpHE7K8IuHZ66kx9RVVghhLEKVU39YnzJWH1/P/+ayFMnyIyo/capdKud8pNoj0qZ6qXKYfu++3veqhvlyJQdp+qg7ViZUjkX3O1Yk3B6iXoBG0j0mqO011pmQVTJa5eitJL1jRZqQdkHWO1aMTdprdpuUUzmsOb//4aa5anVWV09VDjemhN1KhZw6loC9HO7OXfe9HDY/svKTptqpco6HVopBeVOC/pIWdG9VTr9q+FoqJ2FlconCHSupyjnumWlKgLx+v2y4qYfwHXbaiTMXZuUE5ei2Rc4ZRgmRvelXOU3VfnLn6Kg1utpGuIrhglICUa/sbImimxB0QVKVI+53K0YmNLfKYc2xJjhRKzSt1pYv5B7fsRKMKbujqNjzxXLTz+Ww+RGWnzDVbpVzPvxiL6Apf3+5p19iHuvbHat+1fC17lglrExRoszCgMoxnqk3B7mLFeWbbO0hlJhs70EqNloL5ExgDV3LGXUeUaxQi5Nf5ahtHOPShpTRsjmFaYbsoC7mlECUpDLOy7pAqnJUn2P6nYyRC82tcnhzlAk25yLT6mH8N8n1niK78IJwAc7x6WNmTEm6VfYt3NhYbvzpYyY/4vITpdqjcvTlJrQpT3/x0++Bm8fI4RPZ7zGfUOlTDV/v08fpKlM2h9tzql5zw+WOfuEBgGvQVLOuKkf87euAuTI5qWPp03esAE9cv6f7ttGNY4n7Jjkq8xZA5QCQEkrkBPxujuw/6fGPPv0G0M3+K+BN81MqMf0ett73uobj/isgKvMWQOUAkJ3t5kcqU+z/ji+XOMvv7eZnaLGE/cKD8ZMO5C883DY/pRLV70xvDq+GuXK1K7B/Ud8tUDkAZGe/213jZ5BX6/1uV0gsg81PqaCGhx713QKVA8A12O/2281vrrl1td5ufq42UeaNZfj5KRXU8NCjvk+gcgAAAABQJlA5AAAAACgTqBwAAAAAlAlUDgAAAADKBCoHAAAAAGUClQMAAACAMoHKAQAAAECZ/A+2rcNQDQOswwAAAABJRU5ErkJggg==" alt="" />

思路:用Stack基本操作完成。

要检测输入字符是否满足这个条件,一个非常合适的数据结构是stack,后进先出的特征正好满足检测的需求。在检测的时候,每次检查一个字符,如果是左括号,就入栈,如果是右括号,并且右括号和当前栈顶符号是左右配对的,那么就弹出栈顶并且进行下一次检测,如果不满足上面两种情况,就说明检查到了一个非法字符,返回false.

public class Solution {
public boolean isValid(String s) {
if(s.length()==0){
return true;
}
Stack<Character> st=new Stack<Character>();
st.push(s.charAt(0));
for(int i=1;i<s.length();i++){
if(!st.empty()&&isMatch(st.peek(),s.charAt(i))){
st.pop();
}else
st.push(s.charAt(i));
}
if(st.empty()){
return true;
}
return false;
} public static boolean isMatch(char s,char p){
if((s=='('&&p==')')||(s=='['&&p==']')||(s=='{'&&p=='}')){
return true;
}else
return false;
}
}