Question

Formatted question description: https://leetcode.ca/all/65.html

65	Valid Number

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.

Algorithm

Maintain a two-dimensional dp array, where dp[i][j] represents the minimum path sum to the current position.

Next, look for the state transition formula, because there are only two cases to reach the current position (i, j), either from the top (i-1, j) or from the left (i, j-1), we choose the dp value The smaller path is to compare dp[i-1][j] with dp[i][j-1], and add the smaller value to the current number grid[i][j], which is the current position dp value.

However, some special cases need to be assigned in advance, such as the starting point position, which is directly assigned to grid[0][0], and the first row and column. The position of the first row can only come from the left, and the position of the first column The position can come from above, so these two lines should be initialized in advance, and then update from the position (1, 1) to the lower right corner.

Code

Java

public class Valid_Number {

	public static void main(String[] args) {

		String s = "3";

        boolean yes = s.matches("^\\s*[+-]?(\\d+\\.?\\d*|\\d*\\.\\d+)(e[+-]?\\d+)?\\s*$");

//		boolean yes = s.matches("\\de\\d+");

		System.out.print(yes);

	}

	public class Solution {
	    public boolean isNumber(String s) {

	        // @note: matches()
	        // return s.matchAll();

	        //     s.matches("^\\s*[+-]?(\\d+\\.?\\d*|\\d*\\.\\d+)(e[+-]?\\d+)?\\s*");
	        return s.matches("^\\s*[+-]?(\\d+\\.?\\d*|\\d*\\.\\d+)(e[+-]?\\d+)?\\s*$");


	        /*
	                Input:	"."
	                Output:	true
	                Expected:	false
	        */
	        // make it 2 parts, with "e" and without "e"
	        // return s.matches("^\\s*[+-]?d*\\.?\\d*\\s*$") || s.matches("^\\s*[+-]?\\d+e[+-]?\\d+\\s*$");
	    }
	}

}

// OJ: https://leetcode.com/problems/valid-number/
// Time: O(N)
// Space: O(N)
class Solution {
    bool isInteger(string s) {
        if (s.empty()) return false;
        int i = 0, N = s.size();
        if (s[i] == '+' || s[i] == '-') ++i;
        if (i == N) return false;
        while (i < N && isdigit(s[i])) ++i;
        return i == N;
    }
    bool isDecimal(string s) {
        if (s.empty()) return false;
        int i = 0, N = s.size();
        if (s[i] == '+' || s[i] == '-') ++i;
        if (i == N) return false;
        bool hasInteger = isdigit(s[i]);
        while (i < N && isdigit(s[i])) ++i;
        if (i == N || s[i] != '.') return false;
        ++i;
        if (i == N) return hasInteger;
        while (i < N && isdigit(s[i])) ++i;
        return i == N;
    }
public:
    bool isNumber(string s) {
        auto eIndex = s.find_first_of("eE");
        if (eIndex == string::npos) return isDecimal(s) || isInteger(s);
        auto first = s.substr(0, eIndex), second = s.substr(eIndex + 1);
        return (isDecimal(first) || isInteger(first)) && isInteger(second);
    }
};

class States(object):
  def __init__(self):
    self.init = 0
    self.decimal = 1
    self.decpoint = 2
    self.afterdp = 3
    self.e = 4
    self.aftere = 5
    self.sign = 6
    self.nullpoint = 7
    self.esign = 8
    self.afteresign = 9


class Solution(object):
  def isNumber(self, s):
    """
    :type s: str
    :rtype: bool
    """
    s = s.strip()
    states = States()
    state = states.init
    decimals = "01234567890"

    for c in s:
      if state == states.init:
        if c == ".":
          state = states.nullpoint
        elif c in decimals:
          state = states.decimal
        elif c in ["+", "-"]:
          state = states.sign
        else:
          return False
      elif state == states.sign:
        if c in decimals:
          state = states.decimal
        elif c == ".":
          state = states.nullpoint
        else:
          return False
      elif state == states.esign:
        if c not in decimals:
          return False
        state = states.afteresign
      elif state == states.afteresign:
        if c not in decimals:
          return False
      elif state == states.nullpoint:
        if c not in decimals:
          return False
        state = states.decpoint
      elif state == states.decimal:
        if c in decimals:
          continue
        elif c == "e":
          state = states.e
        elif c == ".":
          state = states.decpoint
        else:
          return False
      elif state == states.decpoint:
        if c in decimals:
          state = states.afterdp
        elif c == "e":
          state = states.e
        else:
          return False
      elif state == states.afterdp:
        if c in decimals:
          continue
        elif c == "e":
          state = states.e
        else:
          return False
      elif state == states.e:
        if c in decimals:
          state = states.aftere
        elif c in ["+", "-"]:
          state = states.esign
        else:
          return False
      elif state == states.aftere:
        if c not in decimals:
          return False
      else:
        return False
    return state not in [states.init, states.e, states.nullpoint, states.sign, states.esign]

65 - Valid Number

Question

Algorithm

Code

All Problems

All Solutions