【LeetCode - Java】20. Valid parentheses (simple)

2022-01-26 22:10:06 Beeemo

2. Their thinking

The title is relatively simple , classical Their thinking Is the use Stack , From the string Take out the characters in turn and match them with the top of the stack , Unmatched symbols Into the stack , Symbols that can match Out of the stack , Finally, if The stack is empty. Indicates that all parentheses in the string can perfect match .

The problem is coming. , How to judge Whether the two characters are Match relationship Well ？ Take a look at ASCII surface , Find out `(` And `)` Of ASCII Code difference 1,`[` And `]` and ```{ ``` And `}` Of ASCII All codes are different 2, So this became my The basis of judgment . Other solutions also use `HashMap` Realized , But personally, I still think using ASCII More convenient .

stay Java Three solutions have been tried in the implementation , Namely Stack 、 Arrays and linked lists , But the main idea is still stack First in, then out Characteristics of .

3. Code implementation

3.1 Stack （Stack）

``````	public boolean isValid(String s) {

Stack<Character> chars = new Stack<Character>();
if (s.length() % 2 == 0) {

for (int i = 0; i < s.length(); i++) {

if (!chars.empty()) {

if (s.charAt(i) - chars.peek() == 2 || s.charAt(i) - chars.peek() == 1)
chars.pop();
else
chars.push(s.charAt(i));
} else
chars.push(s.charAt(i));
}
return chars.empty();
} else
return false;
}
``````

3.2 Array （ArrayList）

``````public boolean isValid(String s) {

List<Character> characters = new ArrayList<>();
int l = s.length();
if (l % 2 == 0) {

for (int i = 0; i < l; i++) {

if (!characters.isEmpty()) {

if (s.charAt(i) - characters.get(characters.size() - 1) == 1 || s.charAt(i) - characters.get(characters.size() - 1) == 2)
characters.remove(characters.size() - 1);
else
} else
}
return characters.isEmpty();
} else
return false;
}
``````

``````public boolean isValid(String s) {

if (s.length() % 2 == 0) {

for (int i = 0; i < s.length(); i++) {

if (!chars.isEmpty()) {

if (s.charAt(i) - chars.getLast() == 2 || s.charAt(i) - chars.getLast() == 1)
chars.removeLast();
else
} else
}
return chars.isEmpty();
} else
return false;
}
``````

3.4 contrast

obviously , Between the three schemes There is almost no difference between good and bad , Performance is also Almost unanimously , The time complexity is zero O(n),n Is the length of the string . Then I looked at it Official interpretation It's the same thing Ideas , But we haven't found an algorithm with higher efficiency and less space yet .