1. 有效的括號Ⅰ
有“()”,"[]","{}"三種括號

public boolean isValid(String s){ ? ?Deque<Character> deque = new LinkedList<>(); ? ?char ch; ? ?for(int i = 0; i < s.length(); i++){ ? ? ? ?ch = s.charAt(i); ? ? ? ?//碰到左括號，就把相應(yīng)的右括號入棧 ? ? ? ?if(ch == '('){ ? ? ? ? ? ?deque.push(')'); ? ? ? ?}else if(ch == '{'){ ? ? ? ? ? ?deque.push('}'); ? ? ? ?}else if(ch =='['){ ? ? ? ? ? ?deque.push(']'); ? ? ? ?}else if(deque.isEmpty() || deque.peek() != ch){ ? ? ? ? ? ?return false; ? ? ? ?}else{ ? ? ? ? ? ?deque.pop(); ? ? ? ?} ? ?} ? ?return deque.isEmpty(); }

2. 有效的括號Ⅱ

有,(,)三種，可以任意匹配或不匹配

在有星號的情況下，需要兩個棧分別存儲左括號和星號。從左到右遍歷字符串，進(jìn)行如下操作。

• 如果遇到左括號，則將當(dāng)前下標(biāo)存入左括號棧。

• 如果遇到星號，則將當(dāng)前下標(biāo)存入星號棧。

• 如果遇到右括號，則需要有一個左括號或星號和右括號匹配，由于星號也可以看成右括號或者空字符串，因此當(dāng)前的右括號應(yīng)優(yōu)先和左括號匹配，沒有左括號時和星號匹配：

• 如果左括號棧不為空，則從左括號棧彈出棧頂元素；

• 如果左括號棧為空且星號棧不為空，則從星號棧彈出棧頂元素；

• 如果左括號棧和星號棧都為空，則沒有字符可以和當(dāng)前的右括號匹配，返回false。

遍歷結(jié)束之后，左括號棧和星號?？赡苓€有元素。為了將每個左括號匹配，需要將星號看成右括號，且每個左括號必須出現(xiàn)在其匹配的星號之前。當(dāng)兩個棧都不為空時，每次從左括號棧和星號棧分別彈出棧頂元素，對應(yīng)左括號下標(biāo)和星號下標(biāo)，判斷是否可以匹配，匹配的條件是左括號下標(biāo)小于星號下標(biāo)，如果左括號下標(biāo)大于星號下標(biāo)則返回。

最終判斷左括號棧是否為空。如果左括號棧為空，則左括號全部匹配完畢，剩下的星號都可以看成空字符串，此時 s 是有效的括號字符串，返回true。如果左括號棧不為空，則還有左括號無法匹配，此時 s 不是有效的括號字符串，返回 false。

class Solution{ ? ?public boolean checkValidString(String s){ ? ? ? ?Deque<Integer> leftStack = new LinkedList<Integer>(); ? ? ? ?Deque<Integer> asteriskStack = new LinkedList<Integer>(); ? ? ? ?int n = s.length(); ? ? ? ?for(int i = 0; i < n; i++){ ? ? ? ? ? ?char c = s.charAt(i); ? ? ? ? ? ?if(c == '('){ ? ? ? ? ? ? ? ?leftStack.push(i); ? ? ? ? ? ?}else if(c == '*'){ ? ? ? ? ? ? ? ?asteriskStack.push(i); ? ? ? ? ? ?}else{ ? ? ? ? ? ? ? ?if(!leftStack.isEmpty()){ ? ? ? ? ? ? ? ? ? ?leftStack.pop(); ? ? ? ? ? ? ? ?}else if(!asteriskStack.isEmpty()){ ? ? ? ? ? ? ? ? ? ?asteriskStack.pop(); ? ? ? ? ? ? ? ?}else{ ? ? ? ? ? ? ? ? ? ?return false; ? ? ? ? ? ? ? ?} ? ? ? ? ? ?} ? ? ? ?} ? ? ? ?while(!leftStack.isEmpty() && !asteriskStack.isEmpty()){ ? ? ? ? ? ?int leftIndex = leftStack.pop(); ? ? ? ? ? ?int asteriskIndex = asteriskStack.pop(); ? ? ? ? ? ?if(leftIndex > asteriskIndex){ ? ? ? ? ? ? ? ?return false; ? ? ? ? ? ?} ? ? ? ? ? ?return leftStack.isEmpty(); ? ? ? ?} ? ?} }

3. 有效括號字符串Ⅲ
最長有效括號字符串，僅有'('和')'

具體做法是我們始終保持棧底元素為當(dāng)前已經(jīng)遍歷過的元素中「最后一個沒有被匹配的右括號的下標(biāo)」，這樣的做法主要是考慮了邊界條件的處理，棧里其他元素維護(hù)左括號的下標(biāo)：

• 對于遇到的每個‘(’ ，我們將它的下標(biāo)放入棧中

• 對于遇到的每個 ‘)’ ，我們先彈出棧頂元素表示匹配了當(dāng)前右括號：

  我們從前往后遍歷字符串并更新答案即可。

• 如果棧為空，說明當(dāng)前的右括號為沒有被匹配的右括號，我們將其下標(biāo)放入棧中來更新我們之前提到的「最后一個沒有被匹配的右括號的下標(biāo)」

• 如果棧不為空，當(dāng)前右括號的下標(biāo)減去棧頂元素即為「以該右括號為結(jié)尾的最長有效括號的長度」

需要注意的是，如果一開始棧為空，第一個字符為左括號的時候我們會將其放入棧中，這樣就不滿足提及的「最后一個沒有被匹配的右括號的下標(biāo)」，為了保持統(tǒng)一，我們在一開始的時候往棧中放入一個值為 ?1 的元素。

class Solution { ? ?public int longestValidParentheses(String s) { ? ? ? ?int maxans = 0; ? ? ? ?Deque<Integer> stack = new LinkedList<Integer>(); ? ? ? ?stack.push(-1); ? ? ? ?for (int i = 0; i < s.length(); i++) { ? ? ? ? ? ?if (s.charAt(i) == '(') { ? ? ? ? ? ? ? ?stack.push(i); ? ? ? ? ? ?} else { ? ? ? ? ? ? ? ?stack.pop(); ? ? ? ? ? ? ? ?if (stack.isEmpty()) { ? ? ? ? ? ? ? ? ? ?stack.push(i); ? ? ? ? ? ? ? ?} else { ? ? ? ? ? ? ? ? ? ?maxans = Math.max(maxans, i - stack.peek()); ? ? ? ? ? ? ? ?} ? ? ? ? ? ?} ? ? ? ?} ? ? ? ?return maxans; ? ?} }

原文鏈接：https://www.dianjilingqu.com/441422.html