My c++ solution using DFA


  • 0
    Y

    You can use this url to see image of the DFA
    http://postimg.org/image/5vtgmnqs1/

    bool isNumber(string s) {
        int sz = s.length(), l = 0, r = sz-1;
        for(;l<sz && s[l] == ' ';l++);
        for(;r>=0 && s[r] == ' ';r--);
        if(l>r) return false;
        string zero_to_9 = "0123456789", plus_minus = "+-", dot = ".", e = "e";
        unordered_map<char, int> labels = {
            {'0', 0}, //0-9 are in group 0
            {'1', 0},
            {'2', 0},
            {'3', 0},
            {'4', 0},
            {'5', 0},
            {'6', 0},
            {'7', 0},
            {'8', 0},
            {'9', 0},
            {'+', 1}, //+,- are in group 1
            {'-', 1},
            {'.', 2}, //. is in group 2
            {'e', 3} //e is in group 3
        };
        vector<vector<int> > transitions = {
            //transition[i][j] means when current state is i and when current char is in group j
            {2, 1, 6, -1},
            {2, -1, 6, -1},
            {2, -1, 3, 5},
            {4, -1, -1, 5},
            {4, -1, -1, 5},
            {7, 8, -1, -1},
            {4, -1, -1, -1},
            {7, -1, -1, -1},
            {7, -1, -1, -1}
        };
        int curr = 0;
        for(;l<=r;l++){
            vector<int> temp = transitions[curr];
            if(labels.find(s[l]) == labels.end()) return false;
            int next = temp[labels[s[l]]];
            if(next == -1) return false;
            curr = next;
        }
        return curr == 2 || curr == 4 || curr == 3 || curr == 7;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.