preface

Gold three silver four, and the best time to change the job, I fantasized that as long as jump groove, can leave this “bird place”, with more money, do the most cool thing…

However, the reality is always cruel, recently there was a student girl in the job change, before the interview what handwritten Priomise, Vue two-way binding principle,webpack optimization method, prepared a lot of, I thought I had it in hand, but the result was a big loss in the algorithm, the desired offer did not get, once doubted life. What kind of algorithm would make an interviewer tell a girl that you’ve been working for three years? Tough talk like that?

Valid parenthesis problem

This is an original question in LeetCode, which is intended to test the candidate’s knowledge of stack data structure. So let’s look at the problem

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

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

The sample

The sample1: Enter: s ="()"Output:trueThe sample2: Enter: s ="[the] {} ()"Output:trueThe sample3: Enter: s ="(]"Output:falseThe sample4: Enter: s ="([]"Output:falseThe sample5: Enter: s ="{[]}"Output:true

Copy the code

The problem solving information

If we do not brush the algorithm, do not know so many routines, it is important to get as much information as possible through the questions and examples.

According to the passage, it can be inferred that

  1. The length of string s must be even, it cannot be odd (Pairs matching).
  2. Right parenthesisMust followLeft parenthesis, can meet the matching conditions and have symmetry.
  3. Right parenthesisIf it’s not preceded by an open parenthesis, it’s definitely not a valid parenthesis.

Violence abatement

With all this information in hand, the bighorn thought, since it’s [], {}, () in pairs, can I get rid of them one by one? If the result is an empty string, doesn’t that mean it’s true?

For example

Enter: s = "{[()]}" first step: can eliminate () pair, result s is left {[]} second step: can eliminate [] pair, result s is left {} third step: can eliminate {} pair, result s is left"Copy the code

Code implementation

const isValid = (s) = > {
  while (true) {
    let len = s.length
    // Replace string pairs with '' one by one
    s = s.replace('{}'.' ').replace('[]'.' ').replace('()'.' ')
    // There are two cases where s.length is equal to len
    // 1. S is an empty string
    // 2. S cannot continue matching, resulting in the same length as len at the beginning. For example, ({], len was 3 at the beginning, but still 3 at the end, indicating that no further matching is required, resulting in false
    if (s.length === len) {
      return len === 0}}}Copy the code

The violence elimination method will finally pass the Leetcode use case, but the performance is poor, haha

Stack the problem solving method

Item 2 of the answer information emphasizes symmetry, and the stack (last in, first out) is exactly the opposite of the stack, forming a distinct symmetry.

In: ABC, out: CBA

abc
cba

Copy the code

So try parsing from a stack perspective:

Enter: s ="{[()]}"Step 1: read ch = {, belongs to the left parenthesis, stack, stack at this time there is {the second step: read ch = [, belongs to the left parenthesis, stack, stack at this time there a {[step 3: read ch = (, belongs to the left parenthesis, stack, stack at this time there is {[(step 4: Ch =), in close parentheses, try to read the top element of the stack (and) exactly match, will ({[5: read ch =], in close parentheses, try to read the top element of the stack (and) exactly match, will [[5: read ch =], in close parentheses, try to read the top element of the stack (and) exactly match, will [[6: read ch =], in close parentheses, try to read the top element of the stack (and) exactly match, will [ Ch =}, in close parentheses, try to read the top element of the stack {and} exactly match, push {off the stack, then there is still space in the stack' 'Step 7: In-stack only' 'S ="{[()]}"Conforms to a valid parenthesis definition and returnstrue

Copy the code

Code implementation

const isValid = (s) = > {
  // An empty string meets the condition
  if(! s) {return true
  }

  const leftToRight = {
    '(': ') '.'[': '] '.'{': '} '
  }
  const stack = []

  for (let i = 0, len = s.length; i < len; i++) {
    const ch = s[i]
    / / left parenthesis
    if (leftToRight[ch]) {
      stack.push(ch)
    } else {
      // The close parentheses begin to match
      // 1. If there are no open parentheses in the stack, just false
      // 2. There is data but the top element is not the current close bracket
      if(! stack.length || leftToRight[ stack.pop() ] ! == ch) {return false}}}// Check if there are any elements in the stack
  return! stack.length }Copy the code

Although the violent solution is consistent with our daily thinking, but really stack structure solution is much better.

At the end

In the interview, whether the algorithm should become an important indicator of the assessment of candidates we do not make fun of, but in recent years almost every big factory put the algorithm into the front end of the interview, in order to get the offer, review the data structure, brush questions is still necessary, I wish you and I are gentle algorithm.