“This is the 11 days of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved by Swift language. What is updated in this paper is the valid parentheses of 020 in question 11 of HOT100 in LeetCode.

The title

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective. A valid string must meet the following requirements:

• An open parenthesis must be closed with a close parenthesis of the same type.
• The left parentheses must be closed in the correct order.

Example 1:

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

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

Tip:

1 <= s.length <= 104 s consists only of parentheses '()[]{}'Copy the code

Analysis of the

The purpose of this question is to determine whether the left and right parentheses in a string meet the requirements. Here we need to pay attention to the equal number of open parentheses and corresponding close parentheses. In addition, we also need to pay attention to the position of the open parentheses and corresponding close parentheses, which is symmetrical but interleaved in example 4. So, in order to solve this problem, we adopt the stack ideas to solve the problem, we read a string from left to right and left parenthesis, will it into the stack, and meets the right parenthesis, is to determine whether the current stack elements corresponding left parenthesis, if not then don’t say, direct returns false, if it is will stack elements in the stack, continue to read at a later time. Specific ideas are as follows:

Initialize a dictionary (matches) to hold the unmatched open parentheses in an empty array stack (matches). Initialize ch as the first character of the string. If ch is a close parenthesis, check whether the last element in the stack matches ch. If ch does not match, return false, over. If a match is made, delete the last element in the stack. 4. If there is no over, move ch one element after ch and continue to step 2 to Step 4 until over or the end of the string. 5Copy the code

Answer key

class KLLC020 {

    func isValid(_ s: String) -> Bool {
        // Because the left and right parentheses are paired, false is returned if the string has an odd number of characters
        if s.count % 2 = = 1 {
            return false
        }
        // Initialize the left and right parentheses
        let matches:Dictionary<Character.Character> = [
            ")":"("."]":"["."}":"{"
        ]
        // Initializes the unmatched left parenthesis array
        var stack = [Character] ()for ch in s {
            if ch = = "(" || ch = = "[" || ch = = "{" {
                // If the parenthesis is left, it is added directly to the end of the stack
                stack.append(ch)
            } else {
                // If it is a close parenthesis, check whether it matches the left parenthesis at the top of the stack. If it does not match, over; if it does, delete the left parenthesis element at the top of the stack
                let matchCh:Character = matches[ch] ?? ""
                let topCh:Character = stack.last ?? "a"
                if matchCh ! = topCh {
                    return false
                } else {
                    stack.removeLast()
                }
            }
        }
        // If the stack is empty after the traversal, all matches are successful. Otherwise, the stack fails
        return stack.isEmpty
    }
}
Copy the code