This is the third day of my participation in the More text Challenge. For details, see more text Challenge

65. Significant numbers

The title

The significant numbers (in order) can be divided into the following parts:

• A decimal or an integer
• (Optional) an ‘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 dot ‘.’ 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 significant figures are listed as follows:

• [” 2 “, “0089”, “0.1”, “+ 3.14”, “4”, “- 9”, “2 e10”, “- 90 e3”, “3 e + 7”, “+ 6 e – 1”, “53.5 e93”, “123.456 e789”]

Some invalid numbers are listed as follows:

• [” ABC “, “1 a”, “1 e”, “e3”, “99 e2. 5”, “- 6”, “- + 3”, “95 a54e53”]

You are given a string s, return true if s is a valid number.

The sample

Input: s = "0" Output: true Input: s = "e" Output: false Input: s = "." Output: false Input: s = ".1" Output: trueCopy the code

prompt

1 <= s.length <= 20 s Contains only letters (upper and lower case), numbers (0-9), plus '+', minus '-', or the dot '.'.Copy the code

Analysis of solution ideas

Mode 1: finite state machine

See similar topic, we can think of is to use the finite state machine to carry on the state transfer, the introduction of the state machine because of the length of the problem will not be introduced, there are not clear partners can search the Internet, a lot of big guys on the Internet summary share are very detailed.

First of all, let’s identify the character types here: digit 0-9, positive and negative sign +−, decimal point., power symbol eE.

Define the following nine states in the order from left to right of the string, and the correct states to encounter.

0. Initial state: plus or minus sign -1, number -2, decimal point -3
1. There are pluses and minuses: number -2, decimal point -3
2. No sign: number -2, decimal point -4, power -5
3. Decimal point without prefix: the number -4
4. Prefixed decimal point/number: number -4, power -5
5. Power: number -7, plus or minus sign -6
6. Power sign: the number -7
7. Numbers after power signs: the number -7
8. The letter

As can be seen from the figure, the legal end states are 2,4,7.

code

class Solution {
    public boolean isNumber(String s) {
        // State definition, the 9th state does not meet the condition, directly return the result
        Map[] states = {
            new HashMap<>() {{ put('s'.1); put('d'.2); put('. '.3); }}, / / 0
            new HashMap<>() {{ put('d'.2); put('. '.3); }}, / / 1
            new HashMap<>() {{ put('d'.2); put('. '.4); put('e'.5); }}, / / 2
            new HashMap<>() {{ put('d'.4); }}, / / 3
            new HashMap<>() {{ put('d'.4); put('e'.5); }}, / / 4
            new HashMap<>() {{ put('d'.7); put('s'.6); }}, / / 5
            new HashMap<>() {{ put('d'.7); }}, / / 6
            new HashMap<>() {{ put('d'.7); }} / / 7
        };

        // State transition variables
        int p = 0;
        char t;
        
        // Iterate over the string
        for(char c : s.toCharArray()){
            if(c >= '0' && c <= '9'){
                t = 'd';
            } else if(c == '+' || c == The '-'){
                t = 's';
            } else if(c == 'e' || c == 'E'){
                t = 'e';
            } else if(c == '. ') {
                t = c;
            } else {
                return false;
            }
            // Determines whether the current character is the correct follow-up to the previous state
            if(! states[p].containsKey(t))return false;
            // Update the status
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 4 || p == 7; }}Copy the code

The execution result

Complexity analysis

Time complexity: O(n). Space complexity: O(1).

leetcode-cn.com/problems/va…