DFA. With Explanaition. Easy Java solution based on DFA. O(s.length) time and O(1) space complexity.


  • 0
    O

    For example, if we have DFA M=(Q, A, t, s0, F);
    Q={s0,s1,s2,s3,s4,s5,s6,s7}
    A={'0', '1','2','3','4','5','6','7','8','9', '.', '-', '+', 'e'}
    s0-initial state,
    F={s1,s3,s5,s6}
    DFA
    Based on above DFA graph we have the next transition table

     | [0-9]   | '.' | 'e' | '+', '-' 
    0|   1     | 2   | -   | -       
    1|   1     | 6   | 4   | -        
    2|   3     | -   | -   | -        
    3|   3     | -   | 4   | -        
    4|   5     | -   | -   | 7        
    5|   5     | -   | -   | -        
    6|   6     | -   | 3   | -        
    7|   5     | -   | -   | -        
    

    Before starting we should remove trailing and leading spaces (' ') and also remove '+' and '-' at the front of the string as it doesn't have any influence to the next characters.
    Vote if you like it))

        public boolean isNumber(String s) {
        	int state = 0, i = 0;
        	char ch;
        	s = s.trim();
        	s = s.startsWith("-")||s.startsWith("+")? s.substring(1) : s;
        	while(i < s.length() && state < 8) {
        		ch = s.charAt(i++);
        		switch(state) {
        		    case 0: {
        		        if (ch-48 >= 0 && ch-48 <= 9) state = 1;
        				else if (ch == '.') state = 2;
        				else state = 8;
        		        break;
        		    }
        			case 1: {
        				if (ch == 'e') state = 4;
        				else if (ch-48 >= 0 && ch-48 <= 9) state = 1;
        				else if (ch == '.' && state > 0) state = 6;
        				else state = 8;
        				break;
        			}
        			case 2: {
        				if (ch-48 >= 0 && ch-48 <= 9) state = 3;
        				else state = 8;
        				break;
        			}
        			case 3: {
        				if (ch == 'e') state = 4;
        				else if (ch-48 >= 0 && ch-48 <= 9) state = 3;
        				else state = 8;
        				break;
        			}
        			case 4: {
        			    state = (ch-48 >= 0 && ch-48 <= 9) ? 5 : (ch == '+' || ch == '-' ? 7 : 8);
        			    break;
        	        }
        			case 5: case 7: {
        				state = (ch-48 >= 0 && ch-48 <= 9) ? 5 : 8;
        				break;
        			}
    			    case 6: {
    			        state = ch == 'e' ? 4 : (ch-48 >= 0 && ch-48 <= 9 ? 3 : 8);
    			        break;
    			    }
        		}
        	}
        		
            return state == 1 || state == 3 || state == 5 || state == 6;
        }
    

Log in to reply
 

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