65. Valid Number

Description of the Problem

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution

Tags: Parsing

For any problem about format. I suggest every one first to write a Extended Backus-Naur Form or Regular Expression to represent correct format.

We can split the string by special char such as e, E and . and check the validity of substrings.

Explanation

Extended Backus-Naur Form of Valid Number

\( \langle goal \rangle ::= (\text{'+'} | \text{'-'})? \langle base \rangle ((\text{'e'}|\text{'E'})?\langle expo \rangle )? \)

\(\langle expo \rangle ::= (\text{'+'} | \text{'-'})? \langle digits \rangle \)

\(\langle base \rangle ::= \langle digits \rangle \)

\( \ | \langle digits \rangle \text{'.'} \)

\( \ | \ \text{'.'} \langle digits \rangle \)

\( \ | \langle digits \rangle \text{'.'} \langle digits \rangle \)

\( \langle digits \rangle ::= (\text{'0'} | \text{'1'} | ... | \text{'9'})^+ \)

Code (Rust)

impl Solution {

    fn split_at_char(s: &str, v : char) -> (&str, &str){
        let option_index = s.find(v);

        return match option_index {
            Some(index) => {
                let len = s.len();

                // Exclude the character we found
                return (&s[0..index], &s[index+1..len]);
            },
            None => (s, &""),
        }

    }

    #[inline]
    fn process_first_char( s : &str) -> &str{
        return if s.len() > 0 {
            if s[0..1].find("+").is_some() || s[0..1].find("-").is_some() {&s[1..]} else {s}
        }
        else {
            s
        };
    }

    fn is_digits(s: &str, is_empty_true : bool) -> bool{
        for c in s.chars() {
            match c {
                '0'..='9' => {},
                _ => {return false;},
            }
        }

        return if s == "" { is_empty_true } else { true };
    }

    fn is_signed_digits(s: &str, is_empty_true : bool) -> bool{
        let s = Solution::process_first_char(s);
        return Solution::is_digits(s, is_empty_true);
    }

    // Principal function of Solution
    pub fn is_number(s: String) -> bool {
        if s.len() == 0 {
            return false;
        }

        let s = Solution::process_first_char(&s);

        // Determine 'e' or 'E'
        let char_e = match ( s.find('e'), s.find('E') ) {
            (None,None) => { '\0' }, // dummy value
            (None,Some(_)) => { 'E' },
            (Some(_),None) => { 'e' },
            (Some(_),Some(_)) => { 'e' },
        };

        let (base, expo) = Solution::split_at_char(s, char_e);
        let (lhs, rhs) = Solution::split_at_char(base, '.');

        let (has_dot, has_e) = (
                s.find('.').is_some(),
                s.find('e').is_some() || s.find('E').is_some()
        );

        return match (has_dot, has_e) {

            // Case: <base> ('e'|'E') <expo>
            (true, true) =>
                (lhs.len() > 0 || rhs.len() > 0) &&
                Solution::is_digits(lhs, true) &&
                Solution::is_digits(rhs, true) &&
                Solution::is_signed_digits(expo, false),

            // Case: <lhs>? '.' <rhs>?
            //      => <lhs> '.' <rhs>
            //      => '.' <rhs>
            //      => <lhs> '.'
            (true, false) =>
                (lhs.len() > 0 || rhs.len() >0) &&
                Solution::is_digits(lhs, true) &&
                Solution::is_digits(rhs, true),

            // Case: <base> ('e'|'E') <expo>
            (false, true) =>
                Solution::is_digits(lhs, false) &&
                Solution::is_signed_digits(expo, false),

            // Case: <base>
            (false, false) => Solution::is_digits(lhs, false),

        };
    }

}

Complexity (n is the length of string)

Time complexity:

\( T(n) = \Theta(n) \)

Auxiliary Space:

\( S(n) = O(1) \)

Further Discussion

It is not difficult to see that this type of problems (i.e. Parsing) can be easily to solved by Haskell (Especially if we use Parser library such as ParSec). If I were an interviewee I would argue that it is suitable to use functional programming language instead of the imperative one.

Leetbook