C++ A funny solution with state machine


  • 0
    Y
        class Solution {
        enum State{
            BEGIN = 0,
            AFTER_OP = 1,
            INIT,
            AFTER_NUM_DOT,
            AFTER_DOT,
            AFTER_DOT_NUM,
            AFTER_E,
            AFTER_E_OP,
            AFTER_E_NUM
        };
        
        struct StateMachine {
            map<char, int> conToState;
            bool canEnd;
        };
    public:
        bool isNumber(string s) {
            int size = s.size();
            if(size == 0) return false;
            
            s = deleteSpace(s);
            size = s.size();
            if(size == 0) return false;
            
            vector<StateMachine> stateMachines;
            initStateMachine(stateMachines);
            StateMachine curMachine = stateMachines[BEGIN];
            
            for(int i = 0; i < size; i ++) {
                map<char, int>::iterator iter = curMachine.conToState.find(s[i]);
                if(iter == curMachine.conToState.end()) return false;
                curMachine = stateMachines[iter->second];
            }
            if(curMachine.canEnd) return true;
            return false;
        }
        
        void initStateMachine(vector<StateMachine>& stateMachines) {
            for(int i = 0; i < 9; i ++) {
                StateMachine sm;
                stateMachines.push_back(sm);
            }
            
            batchInsert(stateMachines[BEGIN], AFTER_OP, "+-");
            batchInsert(stateMachines[BEGIN], INIT, "0123456789");
            batchInsert(stateMachines[BEGIN], AFTER_DOT, ".");
            stateMachines[BEGIN].canEnd = false;
            
            batchInsert(stateMachines[AFTER_OP], INIT, "0123456789");
            batchInsert(stateMachines[AFTER_OP], AFTER_DOT, ".");
            stateMachines[AFTER_OP].canEnd = false;
            
            batchInsert(stateMachines[INIT], AFTER_NUM_DOT, ".");
            batchInsert(stateMachines[INIT], INIT, "0123456789");
            batchInsert(stateMachines[INIT], AFTER_E, "e");
            stateMachines[INIT].canEnd = true;
            
            batchInsert(stateMachines[AFTER_NUM_DOT], AFTER_DOT_NUM, "0123456789");
            batchInsert(stateMachines[AFTER_NUM_DOT], AFTER_E, "e");
            stateMachines[AFTER_DOT].canEnd = true;
            
            batchInsert(stateMachines[AFTER_DOT], AFTER_DOT_NUM, "0123456789");
            stateMachines[AFTER_DOT].canEnd = false;
            
            batchInsert(stateMachines[AFTER_DOT_NUM], AFTER_DOT_NUM, "0123456789");
            batchInsert(stateMachines[AFTER_DOT_NUM], AFTER_E, "e");
            stateMachines[AFTER_DOT_NUM].canEnd = true;
            
            batchInsert(stateMachines[AFTER_E], AFTER_E_OP, "+-");
            batchInsert(stateMachines[AFTER_E], AFTER_E_NUM, "0123456789");
            stateMachines[AFTER_E].canEnd = false;
            
            batchInsert(stateMachines[AFTER_E_OP], AFTER_E_NUM, "0123456789");
            stateMachines[AFTER_E_OP].canEnd = false;
            
            batchInsert(stateMachines[AFTER_E_NUM], AFTER_E_NUM, "0123456789");
            stateMachines[AFTER_E_NUM].canEnd = true;
        }
        
        void batchInsert(StateMachine& src, int des, string cons) {
            for(int i = 0; i < cons.length(); i ++) {
                src.conToState[cons[i]] = des;
            }
        }
        
        string deleteSpace(string& s) {
            int i, j;
            for(i = 0; i < s.size(); i ++) {
                if(s[i] != ' ') break;
            }
            
            for(j = s.size() - 1; j >= 0; j --) {
                if(s[j] != ' ') break;
            }
            
            string res = s.substr(i, j - i + 1);
            return res;
        }
    };

Log in to reply
 

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