65. Valid Number

Difficulty:
Related Topics:
Similar Questions:

Problem

Validate if a given string is numeric.

Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10): The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
  var state = [
    {}, 
    {'blank': 1, 'sign': 2, 'digit':3, '.':4}, 
    {'digit':3, '.':4},
    {'digit':3, '.':5, 'e':6, 'blank':9},
    {'digit':5},
    {'digit':5, 'e':6, 'blank':9},
    {'sign':7, 'digit':8},
    {'digit':8},
    {'digit':8, 'blank':9},
    {'blank':9}
  ];
  var validState = [3, 5, 8, 9];
  var currentState = 1;
  var len = s.length;
  var str = '';
  var type = '';
  for (var i = 0; i < len; i++) {
    str = s[i];
    if (str >= '0' && str <= '9') {
      type = 'digit';
    } else if (str === '+' || str === '-') {
      type = 'sign';
    } else if (str === ' ') {
      type = 'blank';
    } else {
      type = str;
    }
    if (state[currentState][type] === undefined) {
      return false;
    } else {
      currentState = state[currentState][type];
    }
  }
    if (validState.indexOf(currentState) === -1) {
    return false;
    } else {
    return true;
    }
};

Explain:

DFA 确定有限状态自动机

Complexity: