The algorithm in LeetCode is pretty much done recently, so it’s time to summarize some interesting things you learned during the process. React looks at a component as a State machine. By interacting with the user, achieving different states, and then rendering the UI to keep the user interface and data consistent.” So what exactly is a state machine?

In this article, we will briefly introduce the concept of state machines, and demonstrate their application by solving an algorithm. We hope to introduce you to the interesting model of state machines, which has a new option when dealing with complex states in programming.

What is a state machine

Finite-state machine (English: Finite-state machine, abbreviated: FSM), also known as finite-state automata, or state machine for short, is a mathematical model that expresses finite states and the transfer and action between these states.

To put it simply, there is a device where the user keeps plugging in input, and the device tells the user whether the input is valid or not. In fact, in the programming process, more or less come into contact with it, just not aware of it. Regex, for example, is a typical use of state machines. Before we look at specific examples, we need to understand the characteristics of the state machine:

The total number of states is finite.

In one state at any one time.

When a condition is triggered, it changes from one state to another.

Now that you’ve introduced the concept of a state machine, you can close this article. It looks boring, doesn’t it? Let’s look at the picture and say:

This is a typical state machine diagram, the circle represents the state in the state machine, the double circle is also a state, but it’s special, it’s the final state, the receiving state. If the final state of the state machine stays in the final state according to the input, it means that the input is acceptable and legal. For example, when the state machine is in S2 state, input 0 into the state machine, then according to the arrow, the state will be transferred to S1, and input 0 will “transfer” to S2, that is, stay where you are and remain unchanged. Note that when a character other than 0 or 1 is entered, the state machine does not have any transitions that match that character, and the input is considered illegal.

OK~ At this point, the basic concept of the state machine is almost understood, the following will be combined with examples to see its practical use.

Application of state machines

As stated above, regex is a typical use of state machines, so let’s implement a simple regex engine that returns whether the input string matches the regular expression:

Given a string (s) and a character pattern (p), implement a system that supports '? The wildcard of 'and '*' matches. '? 'can match any single character. '*' can match any string (including empty strings). A match is successful only if the two strings match exactly. Note: s may be empty and contains only lowercase letters from A to Z. P may be empty and contain only lowercase letters from A to Z, as well as characters? And *.Copy the code

44. Wildcard matching. Stop reading and try to solve this problem. There are a lot of ideas to solve the problem, but since it is regular correlation, then the state machine can definitely solve this problem. Let’s draw a diagram of the state machine to get a feel for it:

Example 1: Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa".Copy the code

According to the regular expression P, this state machine can be drawn:

As shown in the figure above, the initial state of the state machine is S0. When character A is entered, the state of the state machine moves from S0 to S1. Then character A is entered into the state machine.

Let’s look at one more interesting example:

Example 4: Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty string and the second '*' matches the string "dCE ".Copy the code

From the example, this state machine can be drawn:

What’s interesting about this state machine is that there’s no longer just one possibility to move between states, there’s a possibility to move from the same input to different states. Enter the character A into the state machine. Since * can match any string, the state machine can either “stand still” or move to S1. But what if the state machine is only in one state at any one time? In fact, it can be assumed that there are countless state machines waiting to be started. In case of branching, several state machines can be started to transfer corresponding states. Following this idea, at this point we need to start two state machines, one of which has a state at S0 and the other at S1 (transitioned from S0).

After that, no matter input three characters of DCE one by one, the two state machines “stand still”. Finally, input character B. According to the transfer conditions, the first state machine can still stand still, but the second state machine can move to S2 or stand still, so another state machine is started. The state of the third state is S3. The input ends at this point, checks the started state machines, and finds that one of the state machines is final, so the input is valid, and returns true.

Thus, as long as one of the state machines is in the final state, the input is valid (i.e., a match). Now the idea has, it is time to use the code to describe it, might as well try to write their own corresponding procedures. Here is my implementation:

/** * @param {string} s * @param {string} p * @return {boolean} */
var isMatch = function(s, p) {
  // Continuous * is meaningless, it's a simple optimization
  p = p.replace(/\*+/g.The '*');
  // The re describes the corresponding state machine
  const map = {};
  // Initial state
  let index = 0;
  for (const token of p) {
    map[index] = map[index] || {};
    map[index][token] = true;
    // If it is not *, then it can be transferred to the next state as long as it matches
    if(token ! = =The '*') index++;
  }
  // The maximum index is the final state of the state machine
  const SUCCESS = index;
  // A collection of started state machines. The value is the state of the state machine
  let set = new Set(a); set.add(0);
  for (let i = 0; i < s.length; i++) {
    const newSet = new Set(a);const token = s[i];
    for (const status of set) {
      // If the state machine does not have any transition conditions, then there is no need to proceed to the following judgment, scrap the state machine
      if(! map[status])continue;
      // This is the case
      if (map[status][The '*']) newSet.add(status);
      // Can be moved to the next state after matching the corresponding character
      if (map[status]['? '] || map[status][token]) newSet.add(status + 1);
    }
    if(! newSet.size)return false;
    // Replace the old set with a new set of state machines
    set = newSet;
  }
  return set.has(SUCCESS);
};
Copy the code

I annotated all the code, and just a little bit of the overall flow ~ map is the description of the entire state machine. The map’s key is the corresponding state, and the value is an object that describes the path of the transition (that is, those arrows). A set is a set of started state machines, and since each state machine is the same, the difference is their state at the moment, the value of the set is the state of the state machine. The next step is to iterate over the input string, entering character by character into the state machine to make the state machine transition. Finally, check whether there is a final state in the started state machine and return the result ~

The result that comes out of LeetCode is as follows:

summary

The above algorithms have room for optimization, such as state machine reuse, but for better readability of the code, no relevant optimization was carried out. Of course, it can be seen from the results that the running speed of the algorithm is not very ideal, only better than 23% of the submissions. In order to pursue speed, it is more appropriate to solve the problem with the idea of dynamic programming. But using the state machine to answer, the idea is quite clear, but also to deepen the understanding of the state machine. In the future, when you encounter complex state switching and maintenance, you might consider using state machines to solve it.

That’s it! State machines are actually quite interesting models, widely used in front end, back end and even compiler. This article only briefly introduces the related concepts and applications, the detailed content also needs to read the corresponding books ~

Thank you to see the adult here, easy to know, I hope this article is helpful to you ~ thank you!