leetcode题解之有效的括号

• Java
• Python

class Solution {
// Hash table that takes care of the mappings.

private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.

public Solution() {

this.mappings = new HashMap<Character, Character>();

this.mappings.put(‘)‘, ‘(‘);

this.mappings.put(‘}‘, ‘{‘);

this.mappings.put(‘]‘, ‘[‘);

}
public boolean isValid(String s) {
<span class="hljs-comment">// Initialize a stack to be used in the algorithm.</span>
Stack&lt;Character&gt; stack = <span class="hljs-keyword">new</span> Stack&lt;Character&gt;();

<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; s.length(); i++) {
  <span class="hljs-keyword">char</span> c = s.charAt(i);

  <span class="hljs-comment">// If the current character is a closing bracket.</span>
  <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.mappings.containsKey(c)) {

    <span class="hljs-comment">// Get the top element of the stack. If the stack is empty, set a dummy value of ‘#‘</span>
    <span class="hljs-keyword">char</span> topElement = stack.empty() ? <span class="hljs-string">‘#‘</span> : stack.pop();

    <span class="hljs-comment">// If the mapping for this bracket doesn‘t match the stack‘s top element, return false.</span>
    <span class="hljs-keyword">if</span> (topElement != <span class="hljs-keyword">this</span>.mappings.get(c)) {
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    }
  } <span class="hljs-keyword">else</span> {
    <span class="hljs-comment">// If it was an opening bracket, push to the stack.</span>
    stack.push(c);
  }
}

<span class="hljs-comment">// If the stack still contains elements, then it is an invalid expression.</span>
<span class="hljs-keyword">return</span> stack.isEmpty();

}

}

class Solution(object):

def isValid(self, s):

"""

:type s: str

:rtype: bool

"""

    <span class="hljs-comment"># The stack to keep track of opening brackets.</span>
    stack = []

    <span class="hljs-comment"># Hash map for keeping track of mappings. This keeps the code very clean.</span>
    <span class="hljs-comment"># Also makes adding more types of parenthesis easier</span>
    mapping = {<span class="hljs-string">")"</span>: <span class="hljs-string">"("</span>, <span class="hljs-string">"}"</span>: <span class="hljs-string">"{"</span>, <span class="hljs-string">"]"</span>: <span class="hljs-string">"["</span>}

    <span class="hljs-comment"># For every bracket in the expression.</span>
    <span class="hljs-keyword">for</span> char <span class="hljs-keyword">in</span> s:

        <span class="hljs-comment"># If the character is an closing bracket</span>
        <span class="hljs-keyword">if</span> char <span class="hljs-keyword">in</span> mapping:

            <span class="hljs-comment"># Pop the topmost element from the stack, if it is non empty</span>
            <span class="hljs-comment"># Otherwise assign a dummy value of ‘#‘ to the top_element variable</span>
            top_element = stack.pop() <span class="hljs-keyword">if</span> stack <span class="hljs-keyword">else</span> <span class="hljs-string">‘#‘</span>

            <span class="hljs-comment"># The mapping for the opening bracket in our hash and the top</span>
            <span class="hljs-comment"># element of the stack don‘t match, return False</span>
            <span class="hljs-keyword">if</span> mapping[char] != top_element:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment"># We have an opening bracket, simply push it onto the stack.</span>
            stack.append(char)

    <span class="hljs-comment"># In the end, if the stack is empty, then we have a valid expression.</span>
    <span class="hljs-comment"># The stack won‘t be empty for cases like ((()</span>
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">not</span> stack