Leetcode -65- a significant number

[Blog link]

A path to learning at ๐Ÿ”

The nuggets home page

[B].

Significant digits (in order) can be divided into the following parts: a decimal or integer (optional) an 'e' or 'e' followed by an integer Decimal (in order) can be divided into the following parts: (Optional) a signed character ('+' or '-') one of the following formats: At least one digit followed by a dot '.' at least one digit followed by a dot '.' At least one digit Integers (in order) can be divided into the following parts: (Optional) One sign character ('+' or '-') with at least one digit part valid digits 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]" invalid part Numbers listed below: [" ABC ", "1 a", "1 e", "e3", "99 e2. 5", "- 6", "- + 3", "95 a54e53"] to give you a string s, if s is a valid number, please return true. Example 1: Input: s = "0" Output: true Example 2: Input: s = "e" output: false Example 3: Input: s = "." Output: false Example 4: Input: s = ".1" Output: true Hint: 1 <= s.length <= 20 s contains only letters (uppercase and lowercase), digits (0-9), plus '+', minus '-', or the dot '.'. Related Topics Math string ๐Ÿ‘ 212 ๐Ÿ‘Ž 0Copy the code

[็ญ” ๆกˆ]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Multi-condition matching

  • There are too many validation conditions if you debug step by step
  • Given a few test cases here, the T/F classification should cover most scenarios
True: String [] s = new String [] {46. E3 ""," 2 ", "0089", "0.1", "+ 3.14", "4", "- 9", "2 e10", "- 90 e3", "3 e + 7", "+ 6 e - 1", "53.5 e93", "123.456 e789", "- 1"}; False: String s = new String [] [] {", "+ E3" e1 ", "ABC", "1 a", "E3", "99 e2. 5", "- 6", "- + 3", "95 a54e53", "6 e +", "e1", "+"};Copy the code
public boolean isNumber(String s) {
            char[] chars = s.toCharArray();
            boolean sf = false;
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                // If it is not e/ e,+/-,., the number can return false directly
                if(! checkAll(c)) {return false;
                }
                // Digits starting with e must be followed by a signed integer
                if (checkE(c)) {
                    if (i == 0 || checkS(chars[i - 1]) {return false;
                    }
                    // Check if it is a signed integer
                    return checkInt(s.substring(i + 1));
                }
                // Check if there is a signed number
                if (checkS(c)) {
                    if (i == chars.length - 1) {
                        return false;
                    }
                    if (i == 0 || checkE(chars[i - 1]) || checkP(chars[i - 1]) {continue;
                    } else {
                        return false; }}// Check whether integer bits are included
                if (checkN(c)) {
                    continue;
                }
                // Determine if there are decimal places
                if (checkP(c)) {
                    // The decimal point is in the first place
                    if (i == 0 || checkS(chars[i - 1]) {// The following position requires e or an integer containing e
                        return checkEInteger(s.substring(i + 1));
                    } else {
                        if (checkN(chars[i - 1]) {return i == s.length() - 1 || checkPInteger(s.substring(i + 1)); }}}}return true;
        }

        public boolean checkAll(char c) {
            return checkE(c) || checkS(c) || checkN(c) || checkP(c);
        }

        public boolean checkN(char c) {
            return c >= '0' && c <= '9';
        }

        public boolean checkE(char c) {
            return c == 'e' || c == 'E';
        }

        public boolean checkS(char c) {
            return c == '+' || c == The '-';
        }

        public boolean checkP(char c) {
            return c == '. ';
        }

        public boolean checkInt(String s) {
            if ("".equals(s)) {
                return false;
            }
            char[] c = s.toCharArray();
            for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
                if(! checkN(c[i])) {return false; }; }return checkN(c[s.length() - 1]);
        }

        public boolean checkPInteger(String s) {
            if ("".equals(s)) {
                return false;
            }

            char[] c = s.toCharArray();
            if (checkS(c[0]) {return false;
            }
            for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
                if(! checkN(c[i])) {if (checkE(c[i])) {
                        return checkInt(s.substring(i + 1));
                    } else {
                        return false; }}}return true;
        }
        public boolean checkEInteger(String s) {
            if ("".equals(s)) {
                return false;
            }

            char[] c = s.toCharArray();
            if (checkE(c[0]) || checkS(c[0]) {return false;
            }
            for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
                if(! checkN(c[i])) {if (checkE(c[i])) {
                        return checkInt(s.substring(i + 1));
                    } else {
                        return false; }}}return true;
        }
Copy the code

Time complexity O(n)

Idea 2:Water palace antithesis

Time complexity O(n)

Idea 3: Automata

  • This is the subject I flunked in college. I hate to think about it
  • Interested can view the official solution

Time complexity O(n)