Given an input string, determine if it makes a valid number or not. For simplicity, assume that white spaces are not present in the input.
4.325 is a valid number.
1.1.1 is NOT a valid number.
222 is a valid number.
22. is NOT a valid number.
0.1 is a valid number.
22.22. is NOT a valid number.
1. is NOT a valid number.
bool is_number_valid(string s) {//TODO: Write - Your - Codereturn false;}
enum STATE { START, INTEGER, DECIMAL, UNKNOWN, AFTER_DECIMAL};STATE get_next_state(STATE current_state, char ch) {switch(current_state) {case START:case INTEGER: {if (ch == '.') {return DECIMAL;} else if (ch >= '0' && ch <= '9') {return INTEGER;} else {return UNKNOWN;}break;}case DECIMAL:if (ch >= '0' && ch <= '9') {return AFTER_DECIMAL;} else {return UNKNOWN;}break;case AFTER_DECIMAL:if (ch >= '0' && ch <= '9') {return AFTER_DECIMAL;} else {return UNKNOWN;}break;case UNKNOWN:return UNKNOWN;}return UNKNOWN;}bool is_number_valid(const string s) {int i = 0;if (s[i] == '+' || s[i] == '-') {i++;}STATE current_state = START;while (s[i] != '\0') {current_state = get_next_state(current_state, s[i]);if (current_state == UNKNOWN) {return false;}i++;}if (current_state == DECIMAL)return false;return true;}void test(const string s, bool expected) {bool is_valid = is_number_valid(s);if (is_valid) {cout << s << " is valid." << endl;} else {cout << s << " is not valid." << endl;}}int main(int argc, char* argv[]) {test("4.325", true);test("4.325a", false);test("x4.325", false);test("4.32.5", false);test("4325", true);test("1.", false);test("1.1.", false);test("1.1.1", false);test("1.1.1.", false);test("+1.1.", false);test("+1.1", true);test("-1.1.", false);test("-1.1", true);test("", true);}
Linear, O(n).
Constant, O(1).
We’ll use the state machine below to check if a number is valid or not. The initial state is ‘Start’. We’ll process each character to identify the next state. The input string is not a valid number if we reach an UNKNOWN state at any point or if it ends in a DECIMAL.
We are not looking at the sign (+ or -) at the start of a number in the state machine. If there is a sign at the start of the input string, we start processing the string for the state machine after that sign character.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!