Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch card 11 days 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

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.
The sample1: Enter: s ="()"Output:true
Copy the code
The sample2: Enter: s ="[the] {} ()"Output:true
Copy the code
The sample3: Enter: s ="(]"Output:false
Copy the code
The sample4: Enter: s ="([]"Output:false
Copy the code
The sample5: Enter: s ="{[]}"Output:true
Copy the code

Tip:

  • 1 <= s.length <= 104
  • S consists only of parentheses ‘()[]{}’

🌻C# method 1: stack

Create a new stack, iterate over the string, place the open parenthesis on the stack, and match the close parenthesis to the top element. Return false if the parentheses are not of the same type, or remove the top parenthesis if they are.

Finally, if the stack is empty, all parentheses are matched, returning true; Otherwise, return false.

Code:

public class Solution {
     public bool IsValid(string s)
    {
        if (s.Length % 2= =1)
            return false;
        Stack<char> st = new Stack<char> ();for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '(' || s[i] == '[' || s[i] == '{')
                    st.Push(s[i]);
                else if (st.Count == 0 ||
                        s[i] == ') '&& st.Pop() ! ='(' ||
                        s[i] == '] '&& st.Pop() ! ='[' ||
                        s[i] == '} '&& st.Pop() ! ='{')
                    return false;
            }
        return st.Count == 0; }}Copy the code

The execution result

By execution time:64Ms, in all CBeat 96.14% of users in # submissionsMemory consumption:22.2MB, in all CBeat 34.38% of users in # submission
Copy the code

🌻C# method two: hash stack

code

public class Solution {
    public bool IsValid(string s) {
        Stack<char> st = new Stack<char> (); Hashtable ht =new Hashtable(){{') '.'('}, {'} '.'{'}, {'] '.'['}};
        for(int i = 0; i < s.Length; i++) {if(ht.ContainsValue(s[i]))
            {
                st.Push(s[i]);// If it is left parenthesis, push it
            }
            else if(st.Count == 0|| st.Pop() ! = (char)ht[s[i]])// Close parenthesis and stack is empty, or the top of stack does not match the left parenthesis, false
            {
                return false; }}return st.Count == 0;// If the stack is empty and all parentheses are paired, return true}}Copy the code

The execution result

By execution time:72Ms, in all C# beat 79.06% of users in submissionMemory consumption:22.7MB, in all CBeat 13.56% of users in # submissions
Copy the code

🌻Java method 1: stack

The data structure “stack” can be used to determine the validity of parentheses.

We iterate over the given string s. When we encounter an open parenthesis, we expect it to be closed by a close parenthesis of the same type in subsequent traversals. Since the left parenthesis encountered later is closed first, we can place the left parenthesis at the top of the stack.

When we encounter a close parenthesis, we need to close an open parenthesis of the same type. At this point, we can pull out the left parentheses at the top of the stack and determine if they are of the same type. If they are not of the same type, or if there are no open parentheses on the stack, the string s is invalid and returns False.

To quickly determine the type of parentheses, we can use a hash table to store each type of parentheses. The keys of the hash table are close parentheses and the values are open parentheses of the same type.

At the end of the loop, if there are no open parentheses in the stack, we close all the open parentheses in string S, returning True, otherwise returning False.

Note that the length of a valid string must be even, so if the length of the string is odd, we can simply return False without further traversal.

code

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2= =1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(') '.'(');
            put('] '.'[');
            put('} '.'{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if(stack.isEmpty() || stack.peek() ! = pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else{ stack.push(ch); }}returnstack.isEmpty(); }} Link: HTTPS://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
Copy the code

The execution result

By execution time:2Ms, beat out all Java commits70.41% user memory consumption:36.3MB, beat out all Java commits88.02% of the userCopy the code

Complexity analysis

Time complexity: O(n), where nn is the length of the string S space complexity: O((n+∣ σ ∣), where σ stands for character setCopy the code

💬 summary

  • Today is the eleventh day of buckle algorithm clocking!
  • This paper uses C# and Java programming languages to solve the problem
  • Sometimes some methods are written by the god of reference force buckle, but also while learning and sharing, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!