The significant figures (in order) can be divided into the following parts:
A decimal or integer.
Optional) a'e'or'e', followed by an integer.
Decimals (in order) can be divided into the following parts:
Optional) a symbol character ('+'or'-'）
One of the following formats:
At least one digit, followed by a dot'.'
At least one digit, followed by a dot'.'followed by at least one digit.
A point'.', followed by at least one digit.
Integers (in order) can be divided into the following parts:
Optional) a symbol character ('+'or'-'）
At least one digit.
Some of the significant figures are listed below:
2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90e3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
Some of the invalid figures are listed below:
abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
Gives you a string s and returns true if s is a significant number.
Example 1: Enter: s ="0"
Output: true
Example 2: Enter: s ="e"
Output: false
Example 3: Enter: s ="."
Output: false
Example 4: Enter: s =".1"
Output: true
Hint: 1 < = slength <= 20
s contains only English letters (uppercase and lowercase), digits (0-9), plus signs'+', minus'-', or point'.' 。
We can directly traverse it once, and judge whether it is valid while traversing.
If you want to traverse and determine whether it is legitimate, you need to record some key information. For example, when I traversed and came across, then I actually need to know some information, like whether or not there has been a beforeFinish. If it has already appeared, then it can be concluded that the number is illegal.
Except for whether or not theSuch information, we also need to pay attention to other information. Specifically, we need to focus on:
e e is preceded by a number above three information. We can use three variables, one for the last time it was encountered (the index), and -1 for the location that has not yet been encountered.
In fact, the key point of this question is to analyze what is illegal, so what is not illegal, then it is legal. The reason why this is so is because there are so many legal ones, and we have no way to judge them all, but can only start from the perspective of illegality. There are many illegal cases, and how to classify them is a problem, which is why this question is difficult and difficult.
Let's analyze the illegal scenario.
A dot is preceded by an e or dot, such as 11.1 or 3e52e is preceded by an e, like e12e. Or there is no number in front of e, such as e123It is either preceded by an e, or it is preceded by an illegal character. That is, there is a number other than +-ee. Outside of **, we can use three variables:
last dot .Position last e last encountered e e last d last number we need to iterate over the string s, and remember to update the three variables as we iterate.
If we come across a character".", then the need for the front is not".", and there can't be an e, otherwise it's not legal. If e e is encountered, then there cannot be e in front of it. In addition, there are numbers in front of it. If +- is encountered, either it is the first character, or it is preceded by e e, otherwise it cannot be legitimate, and other non-numeric characters are not legitimate, analyze the illegal situation, and use three variables to record the last occurrence of the point, exponent, and the position of the number to copy the judgment.
class solution: def isnumber(self, s: str) -bool: last_dot = last_e = last_d = -1 for i, c in enumerate(s): if c.isdigit():last_d = i elif c == '.': if last_dot != -1 or last_e != -1: return false last_dot = i elif c.lower() == 'e': if last_d == -1 or last_e != -1: return false last_e = i elif c == '+' or c == '-': if i == 0 or s[i-1].lower() == 'e': continue else: return false else: return false return s[-1].isdigit() or (s[-1] == '.' and last_d != -1)Time complexity: $o(n)$Space complexity: $o(1)$
For state machines, what we need to solve is:
What are the options for the state.
It's similar to dynamic programming.For this question, the state of the base is the type of various characters. Namely:
Digit. EE+-Primers are these four types.
There is no need to distinguish between ee and +-, because there is no difference in logic between the two.Then these four are enough. This is not enough. This is because of the description of the title. For example, the title says that e cannot be followed by a decimal. Well for .We need itThere are two states: e preceding theand the . Similarly, for the +- sign, we need to distinguish between the first and the first (immediately adjacent) after e, because the first bit can be followed byNot the one immediately behind e. It's the same with numbers. Since e can't be followed a little, something similar is also neededThe last one is easier to miss, and we need a digital state that can only be followed by numbers, not anything else. For example, +2e+3 at this time, the 3 can only be followed by a number, and everything else is illegal.
For this question:
The four yellow parts of the diagram are the selections. Since +- and [1-9] have no effect on our algorithm, they are not extracted separately, but grouped into a category. The dotted line in the diagram is the state. It's not hard to see,"."The state selection before and after is different. So except:"+-", "[1-9]", "e/e", "."These basic states, we also need to distinguish [1-9], e e is "Before or after. I'm numbering it from left to right, with 1 on the left and 2 on the right, so we have sign1, digit1, exp, d digit2 exp sign2 d.
Note that this is d, not digit2. Because digit2 can be connected to e, a separate state needs to be defined.In addition, since there must be at least one number before and after the dot, and the presence or absence of a number also affects the choice, we also need to distinguish between this. I'm using dot1 here for dots that are preceded by numbers, and dot2 for dots that are preceded by numbers
As for how to transform, I won't analyze them one by one, let's just look at it**. Although the idea is not difficult to understand, there are still quite a lot of details, and everyone will know it by writing it themselves.
To model the state machine, if we know how many states there are, we xxx1 represents the previous xxx and xxx2 represents the following xxx. d indicates that only numbers can be followed.
Language support: python3python3 code:
class solution: def isnumber(self, s: str) -bool: At the heart of any state machine is to model the state machine as follows states = ,"sign1": ,"sign2": ,"digit1": ,"digit2": ,"dot1": , no number in front"dot2": , with numbers in front"exp": ,"d": def get(ch): if ch == ".": return "dot" elif ch in "+-": return "sign" elif ch in "ee": return "exp" elif ch.isdigit():return "digit" state = "start" for c in s: state = states[state].get(get(c)) if not state: return false return "end" in states[state]Time complexity: $o(n)$ Spatial complexity: Although states is used to store the state, it does not increase with the increase of the number, but is a fixed value, so the spatial complexity is $o(1)$