[luffy]_LeetCode20. Valid brackets

LeetCode20. Valid parentheses

Topic request

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

1. The left parentheses must be closed with the same type of the right parentheses.

2. The left parentheses must be closed in the correct order.

The sample

Input: s = "()" output: trueCopy the code

Train of thought

1. Check whether the field s appears in pairs. If not, return false

if (s.length % 2 == 1) return false;
Copy the code

2. Then facilitate the s array, check whether the element is the left parenthesis, and save

let arr = [];
for (let item of s) {  
    if (item == '(' || item == '[' || item == '{') {    
        arr.push(item);  
    }
}
Copy the code

3. Then check if the parentheses belong to the right type, and if so, check if the last element of the ARR array matches the right element being iterated over, if not return false

... else {  
    let arrLen = arr.length - 1;  
    if (item == ')' && arr[arrLen] != '(') return false;  
    if (item == ']' && arr[arrLen] != '[') return false;  
    if (item == '}' && arr[arrLen] != '{') return false;
}
Copy the code

4. If the left element and the last element of the array match a pair of parentheses, the last element of the array is removed. If the length of the array is 0, all the parentheses match a pair of parentheses

. else { ... arr.pop(); } return ! arr.length;Copy the code

The complete code

function isValid(s) { if (s.length % 2 == 1) return false; let arr = []; for (let item of s) { if (item == '(' || item == '[' || item == '{') { arr.push(item);  } else { let arrLen = arr.length - 1; if (item == ')' && arr[arrLen] ! = '(') return false; if (item == ']' && arr[arrLen] ! = '[') return false; if (item == '}' && arr[arrLen] != '{') return false; arr.pop(); } } return !arr.length; }Copy the code