Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

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

A valid string must meet the following requirements:

  • The opening parenthesis must be closed with a closing parenthesis of the same type.
  • The opening brackets must be closed in the correct order.

 

Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false Example 4: Input: s = "([)]" Output: false Example 5: Input: s = "{[]}" output: true tip: 1 < = s.l ength < = 104 s only by brackets' [] {} () 'Copy the code

 

Ii. Thinking analysis:

  • It’s like looking in half, and then replacing, and if both of them can be replaced that means there are pairs of parentheses, or there are single parentheses

Three, AC code

/** * @param {string} s * @return {boolean} */ var isValid = function(s) { let length = s.length / 2; for (let i = 0; i < length; i++) { s = s.replace("()", "").replace("{}", "").replace("[]", ""); } return s.length == 0; }; Status: Elapsed time: 120 ms Memory consumption: 43.2 MBCopy the code

Four,

  • Of course there is more than one way to see the official use stack

Iterates over the given string SS. When we encounter an open parenthesis, we expect a close parenthesis of the same type to close it in subsequent iterations. Since the open parenthesis encountered later must be closed first, we can put this open 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 open bracket at the top of the stack and determine if they are the same type of bracket. If it is not the same type, or if there is no open bracket in the stack, then the string ss is invalid and False is returned.

var isValid = function(s) { const n = s.length; if (n % 2 === 1) { return false; } const pairs = new Map([ [')', '('], [']', '['], ['}', '{'] ]); const stk = []; s.split('').forEach(ch => { if (pairs.has(ch)) { if (! stk.length || stk[stk.length - 1] ! == pairs.get(ch)) { return false; } stk.pop(); } else { stk.push(ch); }}); return ! stk.length; }; Complexity analysis Time complexity: O(n), where nn is the length of the string ss. Space complexity: O(n+∣ sigma ∣), where sigma represents the character set, in this case there are only 66 brackets in the string, ∣ sigma ∣=6. The number of characters in the stack is O(n), and the space of the hash table is O(sigma ∣), and you add it up to get the total space complexity.Copy the code

For reference only

Refer to the topic

  • Force button (LeetCode)