面试题20

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

注意：本题与主站 65 题相同：https://leetcode-cn.com/problems/valid-number/

Solutions

1. DFA

class Solution {
public:
    bool isNumber(string s) {
        int states[9][6] = {
        // states[2][4] = 5 represents state 2 can be converted to state 5 when meets type 4(e). ie: 42.1 -> 42.1e
        // The basic form is: +1.4e+2    states are: 0 -> 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8
        // The special case is state 3: which can be:  " +."   or " .", when meets a number, becomes to 4
        //  edges(transition)
        //  ' '  +/- 1/2  .   e   other
            { 0,  1,  2,  3, -1, -1}, // state 0: begin(with blank)
            {-1, -1,  2,  3, -1, -1}, // state 1: "  +"
            { 8, -1,  2,  4,  5, -1}, // state 2: " 42" or "  +3"                 valid end
            {-1, -1,  4, -1, -1, -1}, // state 3: "  +." or " ."       
            { 8, -1,  4, -1,  5, -1}, // state 4: " +1." or " .5" or "+.4"        valid end
            {-1,  6,  7, -1, -1, -1}, // state 5: " +6.4e" or "-.04e" or "  5e"
            {-1, -1,  7, -1, -1, -1}, // state 6: " +6.4e+" or " .1e+" or "  4e+"
            { 8, -1,  7, -1, -1, -1}, // state 7: " +6.4e12" or " .1e+2"          valid end
            { 8, -1, -1, -1, -1, -1}, // state 8: end(with blank)                 valid end
        };
        unordered_map<char, int> m = {{' ', 0}, {'+', 1}, {'-', 1}, {'.', 3}, {'e', 4}};
        int isvalid[9] = {0, 0, 1, 0, 1, 0, 0, 1, 1};
        function<int(int, char &)> type = [&m](int state, char & c) {
            if (isdigit(c))
                return 2;
            else if (m.count(c))
                return m[c];
            else
                return 5;
        };
        int state = 0;
        for (auto & c : s) {
            state = states[state][type(state, c)];
            if (state == -1)
                return false;
        }
        return isvalid[state];
    }
};

1. straight forward

2. reference : https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/javaban-ben-ti-jie-luo-ji-qing-xi-by-yangshyu6/

class Solution {
public:
    bool isNumber(string s) {
        while (s.size() && s.back() == ' ') s.pop_back();
        if (!s.size()) return false;

        int st = 0;
        while (st < s.size() && s[st] == ' ') st++;
        bool numseen = false, dotseen = false, eseen = false;
        for (int i = st; i < s.size(); i++) {
            if (isdigit(s[i]))
                numseen = true;
            else if (s[i] == '.') {
                // . can only be in the first part
                if (dotseen || eseen) return false;
                dotseen = true;
            }
            else if (s[i] == 'e' || s[i] == 'E') {
                // make sure there is no e before and must has num before
                if (eseen || !numseen)
                    return false;
                eseen = true;
                // make sure there are num after e
                numseen = false;
            }
            else if (s[i] == '-' || s[i] == '+') {
                // -/+ either at the first place or after the e
                if (i > st && !(s[i - 1] == 'e' || s[i - 1] == 'E'))
                    return false;
            }
            else
                return false;
        }

        return numseen;
    }
};