The subject content

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order.

()[]{}, ([{}]), ((){[]}), these are true.

I didn’t have a clear idea after the first reading. After looking at the example, I came to think that there should be two main valid categories, nested symmetries like this ([{}]) and contiguous symmetries like this ({}[]).

But at the same time, there are doubts about whether the form {()[{}]} meets the requirements of symmetry, so the first two categories are dealt with first.

After processing, I found that I was stuck in the kind of case in question.

Wrong answer

var isValid = function(s) {
    if(s.length % 2 === 1 || s.length === 1) {
        return false
    }
    let map = {
        ') ' : '('.'] ' : '['.'} ' : '{'
    }
    if(map[s[1]] === s[0]) {// close symmetryfor (let i = 0; i < s.length - 1;) {
            if(map [s] [I + 1] = = = s [I]) {/ / add 2 because close to symmetry in the form of group I = I + 2}else {
                return false}}return true
    } else if(s[0] === map[s[s.length-1]]){// Nested symmetryfor(leti = 0; i < s.length / 2;) {// Determine whether the element matches the position of the symmetric pointif (s[i] === map[s[s.length - 1 - i]]) {
                i ++ 
            } else {
                return false}}return true
    }
    return false
};
Copy the code

The official method

Unable to go on in the morning, I did not think of a better way, so I had to go to the official solution. Finished clapped, the idea is very clear, the implementation of the required code is also very simple.

After the realization of a look, should brush the problem since the best look beat rate, but the beat rate is actually unstable. The reason for this has also been verified by LeetCode insiders, who quote:

The server runs at different times depending on the load, and the fewer the test sets, the more obvious.

The official solution is analyzed from the beginning to the end of the website. In a nutshell, it is: use a stack to store the open parenthesis currently encountered, and once a close parenthesis matching an existing open parenthesis is encountered, the left parenthesis is removed from the stack. The natural ideal is to loop through the stack with no elements left.

Otherwise, if there is, it means there are mismatched parentheses.

var isValid = function(s) {
    if(s.length % 2 === 1 || s.length === 1) {
        return false
    }
    let arr = []
    let map = {
        '(' : ') '.'[' : '] '.'{' : '} '
    }
    for (let i = 0; i < s.length;) {
        if (s[i] in map) {
            arr.push(s[i])
        } else if (s[i] === map[arr[arr.length - 1]]){
            arr.pop()
        }
        i++
    }
    return arr.length > 0 ? false : true
};
Copy the code

The solution of the idea of qing qi

Rhinoc of LeetCode China provided this solution. After watching the movie, you must clap your thighs.

The solution is that all test cases given will have at least one set of close symmetrical brackets (such as [{}]). So each time the loop gets rid of the symmetric parentheses right next to each other, at the end of the ideal situation as in the official solution, there are no parentheses left.

The code of this solution is also very concise, but probably due to replace, the time complexity and space complexity are not very good.

var isValid = function (s) {
    while (s.length) {
        var temp = s;
        s = s.replace('()'.' ');
        s = s.replace('[]'.' ');
        s = s.replace('{}'.' ');
        if (s == temp) return false
    }
    return true;
}
Copy the code