JavaScript DFA Solution (with graph)


  • 1

    This is DFA of regex [-+]?((\d+\.?)|(\d*\.\d+))(e[-+]?\d+)?

    fig

    /**
     * @param {string} s
     * @return {boolean}
     */
    const isNumber = (s) => {
      /** This transform table is DFA of regex [-+]?((\d+\.?)|(\d*\.\d+))(e[-+]?\d+)?
       * You can get it from http://hackingoff.com/compilers/regular-expression-to-nfa-dfa
       * There are 4 type of input chars:
       * s -+
       * d .
       * n 0-9
       * e eE
       */
      const transformTable = {
        0: {s:1, d:3, n:2},
        1: {     d:3, n:2},
        2: {     d:4, n:2, e:5},
        3: {          n:6},
        4: {          n:6, e:5},
        5: {s:7,      n:8},
        6: {          n:6, e:5},
        7: {          n:8},
        8: {          n:8}
      };
      const endStates = [2, 4, 6, 8];
      const strArr = Array.from(s.trim(s));
    
      let nextState = null;
      for(let char of strArr) {
        let charType = getCharType(char);
        if (!charType) {
          return false;
        }
    
        nextState = nextState!==null ?
            transformTable[nextState][charType] :
            transformTable[0][charType];
        if (nextState === undefined) {
          return false;
        }
      }
    
      return endStates.indexOf(nextState) !== -1;
    };
    
    const getCharType = (c) => {
      const code = c.charCodeAt(0);
      // -+
      if(code === 43 || code === 45) {
        return 's';
      }
      // .
      if(code === 46) {
        return 'd';
      }
      // 0-9
      if(code >= 48 && code <= 57) {
        return 'n';
      }
      // eE
      if(code === 69 || code === 101) {
        return 'e';
      }
      return false;
    };
    

Log in to reply
 

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