本文主要是介绍LeetCode 0065 Valid Number，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题传送门

1. 题目描述

2. Solution 1

1、思路分析
All we need is to have a couple of flags so we can process the string in liner time:
We start with trimming.
If we see [0-9] we reset the number flags.
We can only see . if we didn't see e or .
We can only see e if we didn't see e but we did see a number. We reset numberAfterE flag.
We can only see + and - in the beginning and after an e
any other character break the validation.
At the end it is only valid if there was at least 1 number and if we did see an e then a number after it as
well.

2、代码实现

package Q0099.Q0065ValidNumber;

public class Solution {

    /*
        All we need is to have a couple of flags so we can process the string in liner time:
        We start with trimming.
        If we see `[0-9]` we reset the number flags.
        We can only see `.` if we didn't see `e` or `.`
        We can only see `e` if we didn't see `e` but we did see a number. We reset numberAfterE flag.
        We can only see + and - in the beginning and after an e
        any other character break the validation.
        At the end it is only valid if there was at least 1 number and if we did see an e then a number after it as
        well.

        So basically the number should match this regular expression:
        [-+]?(([0-9]+(.[0-9]*)?)|.[0-9]+)(e[-+]?[0-9]+)?

        The 'numberAfterE' is unnecessary.
     */
    public boolean isNumber(String s) {
        s = s.trim().toLowerCase();

        boolean pointSeen = false;
        boolean eSeen = false;
        boolean numberSeen = false;

        for (int i = 0; i < s.length(); i++) {
            if ('0' <= s.charAt(i) && s.charAt(i) <= '9') {
                numberSeen = true;
            } else if (s.charAt(i) == '.') {
                if (eSeen || pointSeen) return false;
                pointSeen = true;
            } else if (s.charAt(i) == 'e') {
                if (eSeen || !numberSeen) return false;
                numberSeen = false;
                eSeen = true;
            } else if (s.charAt(i) == '-' || s.charAt(i) == '+') {
                if (i != 0 && s.charAt(i - 1) != 'e') return false;
            } else {
                return false;
            }
        }
        return numberSeen;
    }
}

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(1)

3. Solution 2

package Q0099.Q0065ValidNumber;

public class Solution2 {

    public boolean isNumber(String s) {
        return s.trim().matches("[-+]?(\\d+\\.?|\\.\\d+)\\d*([e|E][-+]?\\d+)?");
    }
}

4. Solution 3

1、思路分析
DFA: Deterministic Finite Automaton 确定有限状态自动机
States
0: initial
1: only dot
2: number
3: sign
4: dot number
5: e
6: e sign
7: e number
8: end
9: fail

Inputs
0: others
1: space
2: dot
3: numbers
4: sign
5: e

2、代码实现

package Q0099.Q0065ValidNumber;

import java.util.Arrays;
import java.util.List;

/*
    DFA: Deterministic Finite Automaton 确定有限状态自动机
    States
    0: initial
    1: only dot
    2: number
    3: sign
    4: dot number
    5: e
    6: e sign
    7: e number
    8: end
    9: fail

    Inputs
    0: others
    1: space
    2: dot
    3: numbers
    4: sign
    5: e
 */
public class Solution3 {

    boolean isNumber(String s) {
        int state = 0;
        int[][] transitions = {
//               0, 1, 2, 3, 4, 5
                {9, 0, 1, 2, 3, 9}, // 0
                {9, 9, 9, 4, 9, 9}, // 1
                {9, 8, 4, 2, 9, 5}, // 2
                {9, 9, 1, 2, 9, 9}, // 3
                {9, 8, 9, 4, 9, 5}, // 4
                {9, 9, 9, 7, 6, 9}, // 5
                {9, 9, 9, 7, 9, 9}, // 6
                {9, 8, 9, 7, 9, 9}, // 7
                {9, 8, 9, 9, 9, 9}, // 8
                {9, 9, 9, 9, 9, 9}  // 9
        };

        for (int i = 0; i < s.length(); i++) {
            int input = getInput(s.charAt(i));
            state = transitions[state][input];
            if (state == 9) return false;
        }

        List<Integer> accepts = Arrays.asList(2, 4, 7, 8);
        return accepts.contains(state);

    }

    private int getInput(char c) {
        if (c == ' ') return 1;
        if (c == '.') return 2;
        if (c >= '0' && c <= '9') return 3;
        if (c == '+' || c == '-') return 4;
        if (c == 'e' || c == 'E') return 5;
        return 0;
    }
}

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(1)

这篇关于LeetCode 0065 Valid Number的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！