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

The title

Implement a function that determines whether a string represents a numeric value (both integer and decimal).

The values (in order) can be divided into the following sections:

  1. A number of Spaces
  2. A decimal or an integer
  3. (Optional) an ‘e’ or ‘e’ followed by an integer
  4. A number of Spaces

Decimals (in order) can be divided into the following parts:

  1. (Optional) a symbol character (‘+’ or ‘-‘)
  2. 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:

  1. (Optional) a symbol character (‘+’ or ‘-‘)
  2. At least one digit

Some values are listed as follows:

[” + 100 “, “5 e2”, “123”, “3.1416”, “1 e – 16”, “0123”] part non-numerical listed below:

[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

Source: LeetCode

Train of thought

There are a variety of solutions to this problem: “regular”, “DFA”, “simulation”, here with a more easy to understand the string simulation method

1. This problem is almost exactly the same as that in Leetcode 65, except for the addition of a numeric part (several Spaces), so initially you need to call trim() to remove the whitespace before and after

The string is divided into two parts: e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e),e(e

3. Implement an isChecked method to verify that the string is valid

  • + or – can only be in the first position
  • .only once
  • Numbers appear at least once
      public boolean isNumber(String s) {
        s = s.trim();// Remove the Spaces before and after
        char[] cs = s.toCharArray();
        int n = cs.length;
        int idx = -1;
        //1. Find the first e or the position of e
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == 'e' || cs[i] == 'E') {
                if(idx ! = -1) {
                    return false;  // Note that e(e) appears twice
                } else{ idx = i; }}}boolean ans = true;
        // In this e or e as the center as the partition
        if (idx == -1) {  // If idx=-1, there is no E and E. E (E) must be followed by an integer. It can be preceded by either a decimal or an integer
            ans &= isChecked(cs, 0, n - 1.false);
        } else {
            ans &= isChecked(cs, 0, idx - 1.false);
            ans &= isChecked(cs, idx + 1, n - 1.true);
        }
        return ans;
    }

    public boolean isChecked(char[] cs, int start, int end, boolean mustInt) {
        if (start > end) return false;
        boolean point = false;
        boolean hasNum = false;
        //1. If the first position is +- sign
        if (cs[start] == '+' || cs[start] == The '-') start++;
        for (int i = start; i <= end; i++) {
            if (cs[i] >= '0' && cs[i] <= '9') {
                hasNum = true;
            } else if (cs[i] == '. ' && !point) {
                if (mustInt) return false; // No decimal point if it must be an integer
                point = true;
            } else {
                return false; }}return hasNum;
    }
Copy the code

Time complexity

O(N)

Extra space complexity

O(N) uses cs array storage, of course if you use the charAt method you can reduce the extra space complexity to O(1)