65. Valid Number.md

65. Valid Number

思路

验证给定的字符串是否表示一个合法的数值。

表示数值的字符串一定遵循模式A.BeC，其中A、B、C分别表示整数部分、小数部分和指数部分，e可用大写E替代。例如-12.34e-56，那么A = -12, B = 34, C = -56。

其中A和C是可带符号的而B是无符号的。

为了判断给定的字符串是否能表示一个数值，我们只需从左到右尽可能多的扫描0-9的数位串得到A（可能以+-开头），如果紧接着跟了小数点“.”，那么需要继续尽可能多的扫描0-9数位串得到B，然后如果遇到了“e”或者“E”，再继续尽可能多的扫描0-9数位串得到C（可能以+-开头）。为此我们需要定义两个返回类型都为bool的函数Scan_Signed(string &s)和Scan_Unsigned(string &s)分别用于扫描AC和B，注意传入的是字符串的引用，我们会在函数结束前将s剩余未扫描的部分赋值给s。

需要注意根据测试样例我们可能需要去掉首尾的空格，另外.2和2.这种也是合法的。

只需要一次扫描因此时间复杂度为O(n)，空间复杂度O(1)。

C++

class Solution {
private:
    bool Scan_Unsigned(string &s){
        // if(s.empty()) return false;
        int i = 0;      
        while(i < s.size()){
            if(s[i] < '0' || s[i] > '9') break;
            i++;
        }
        s = s.substr(i); // 将s剩余未扫描的部分赋值给s
        return (i > 0);
    }
    
    bool Scan_Signed(string &s){
        // if(s.empty()) return false;
        if(s[0] == '+' || s[0] == '-') s = s.substr(1);
        return Scan_Unsigned(s);
    }
    
public:
    bool isNumber(string s) {
        // if(s.empty()) return false;

        // 去掉首尾的空格
        int l = 0, r = s.size() - 1;
        while(s[l] == ' ') l++;
        while(l < r && s[r] == ' ') r--;
        s = s.substr(l, r - l + 1);
        
        bool A = Scan_Signed(s);  // 整数部分
        bool dot = (s[0] == '.'); // 小数点
        if(dot) s = s.substr(1);
        bool B = (dot && Scan_Unsigned(s)); // 小数部分
            
        if(!A && !B) return false;          // 如果没有整数部分那么小数部分不能为空
        //if(A && dot && !B) return false;  // "2."这种是合法的, 所以这里注释掉
        //if(!A && dot && B) return false;  // ".2"这种也是合法的, 所以这里注释掉
        
        if(s.empty()) return true;
        
        // 指数部分
        if(s[0] != 'e' && s[0] != 'E') return false;
        s = s.substr(1);
        return Scan_Signed(s) && s.empty();
    }
};

写法二

思路一样，只是分别检查ABC是否为空，AB不能同时为空。

class Solution {
private:
    bool check_unsign_empty(string &s){
        int i = 0;
        while(i < s.size() && s[i] >= '0' && s[i] <= '9') i++;
        if(i > 0) s = s.substr(i);
        return i == 0;
    }
    bool check_sign_empty(string &s){
        if(!s.empty() && s[0] == '-' || s[0] == '+') s = s.substr(1);
        return check_unsign_empty(s);
    }
    
public:
    bool isNumber(string s) { // A.BeC
        // 去掉首尾的空格
        int l = 0, r = s.size() - 1;
        while(s[l] == ' ') l++;
        while(l < r && s[r] == ' ') r--;
        s = s.substr(l, r - l + 1);
                
        bool A_is_empty = true, B_is_empty = true, C_is_empty = true;
        
        A_is_empty = check_sign_empty(s);
        
        if(!s.empty() && s[0] == '.'){
            s = s.substr(1);
            B_is_empty = check_unsign_empty(s);
        }
        
        if(A_is_empty && B_is_empty) return false; // AB不能同时为空
        
        if(!s.empty() && s[0] == 'e'){
            s = s.substr(1);
            C_is_empty = check_sign_empty(s);
            if(C_is_empty) return false;
        }
        
        return s.empty();
    }
};