題目描述（困難難度）

給定一個(gè)字符串，判斷它是否代表合法數(shù)字，當(dāng)然題目描述的樣例不夠多，會(huì)使得設(shè)計(jì)算法中出現(xiàn)很多遺漏的地方，這里直接參考評(píng)論區(qū)@yeelan0319給出的更多測(cè)試樣例。

test(1, "123", true);
test(2, " 123 ", true);
test(3, "0", true);
test(4, "0123", true);  //Cannot agree
test(5, "00", true);  //Cannot agree
test(6, "-10", true);
test(7, "-0", true);
test(8, "123.5", true);
test(9, "123.000000", true);
test(10, "-500.777", true);
test(11, "0.0000001", true);
test(12, "0.00000", true);
test(13, "0.", true);  //Cannot be more disagree!!!
test(14, "00.5", true);  //Strongly cannot agree
test(15, "123e1", true);
test(16, "1.23e10", true);
test(17, "0.5e-10", true);
test(18, "1.0e4.5", false);
test(19, "0.5e04", true);
test(20, "12 3", false);
test(21, "1a3", false);
test(22, "", false);
test(23, "     ", false);
test(24, null, false);
test(25, ".1", true); //Ok, if you say so
test(26, ".", false);
test(27, "2e0", true);  //Really?!
test(28, "+.8", true);  
test(29, " 005047e+6", true);  //Damn = =|||

解法一 直接法

什么叫直接法呢，就是沒有什么通用的方法，直接分析題目，然后寫代碼，直接貼兩個(gè) leetcode Disscuss 的代碼吧，供參考。

想法一。

把當(dāng)前的輸入分成幾類，再用幾個(gè)標(biāo)志位來判斷當(dāng)前是否合法。

public boolean isNumber(String s) {
    s = s.trim();

    boolean pointSeen = false;
    boolean eSeen = false;
    boolean numberSeen = false;
    boolean numberAfterE = true;
    for(int i=0; i<s.length(); i++) {
        if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
            numberSeen = true;
            numberAfterE = true;
        } else if(s.charAt(i) == '.') {
            if(eSeen || pointSeen) {
                return false;
            }
            pointSeen = true;
        } else if(s.charAt(i) == 'e') {
            if(eSeen || !numberSeen) {
                return false;
            }
            numberAfterE = false;
            eSeen = true;
        } else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
            if(i != 0 && s.charAt(i-1) != 'e') {
                return false;
            }
        } else {
            return false;
        }
    }

    return numberSeen && numberAfterE;
}

時(shí)間復(fù)雜度：O（n）。

空間復(fù)雜度：O（1）。

想法二，遍歷過程中，把遇到不符合的都返回 false，到最后成功到達(dá)末尾就返回 true。C++ 的代碼，可以參考一下思想。

bool isNumber(const char *s) 
{
    int i = 0;

    // skip the whilespaces
    for(; s[i] == ' '; i++) {}

    // check the significand
    if(s[i] == '+' || s[i] == '-') i++; // skip the sign if exist

    int n_nm, n_pt;
    for(n_nm=0, n_pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i++)
        s[i] == '.' ? n_pt++:n_nm++;       
    if(n_pt>1 || n_nm<1) // no more than one point, at least one digit
        return false;

    // check the exponent if exist
    if(s[i] == 'e') {
        i++;
        if(s[i] == '+' || s[i] == '-') i++; // skip the sign

        int n_nm = 0;
        for(; s[i]>='0' && s[i]<='9'; i++, n_nm++) {}
        if(n_nm<1)
            return false;
    }

    // skip the trailing whitespaces
    for(; s[i] == ' '; i++) {}

    return s[i]==0;  // must reach the ending 0 of the string
}

時(shí)間復(fù)雜度：O（n）。

空間復(fù)雜度：O（1）。

解法二 自動(dòng)機(jī)

自己最開始想到的就是這個(gè)，編譯原理時(shí)候在學(xué)到的自動(dòng)機(jī)，就是一些狀態(tài)轉(zhuǎn)移。這一塊內(nèi)容很多，自己也很多東西都忘了，但不影響我們寫算法，主要參考這里。

如上圖，從 0 開始總共有 9 個(gè)狀態(tài)，橙色代表可接受狀態(tài)，也就是表示此時(shí)是合法數(shù)字。總共有四大類輸入，數(shù)字，小數(shù)點(diǎn)，e 和 正負(fù)號(hào)。我們只需要將這個(gè)圖實(shí)現(xiàn)就夠了。

public boolean isNumber(String s) {
    int state = 0; 
    s = s.trim();//去除頭尾的空格
    //遍歷所有字符，當(dāng)做輸入
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)) {
             //輸入正負(fù)號(hào)
            case '+':
            case '-':
                if (state == 0) {
                    state = 1;
                } else if (state == 4) {
                    state = 6;
                } else {
                    return false;
                }
                break;
            //輸入數(shù)字
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                //根據(jù)當(dāng)前狀態(tài)去跳轉(zhuǎn)
                switch (state) {
                    case 0:
                    case 1:
                    case 2:
                        state = 2;
                        break;
                    case 3:
                        state = 3;
                        break;
                    case 4:
                    case 5:
                    case 6:
                        state = 5;
                        break;
                    case 7:
                        state = 8;
                        break;
                    case 8:
                        state = 8;
                        break;
                    default:
                        return false;
                }
                break;
            //小數(shù)點(diǎn)
            case '.':
                switch (state) {
                    case 0:
                    case 1:
                        state = 7;
                        break;
                    case 2:
                        state = 3;
                        break;
                    default:
                        return false;
                }
                break;
            //e
            case 'e':
                switch (state) {
                    case 2:
                    case 3:
                    case 8:
                        state = 4;
                        break;
                    default:
                        return false;
                }
                break;
            default:
                return false;

        }
    }
    //橙色部分的狀態(tài)代表合法數(shù)字
    return state == 2 || state == 3 || state == 5 || state == 8;
}

時(shí)間復(fù)雜度：O（n）。

空間復(fù)雜度：O（1）。

解法三 責(zé)任鏈模式

解法二看起來已經(jīng)很清晰明了了，只需要把狀態(tài)圖畫出來，然后實(shí)現(xiàn)代碼就很簡(jiǎn)單了。但是缺點(diǎn)是，如果狀態(tài)圖少考慮了東西，再改起來就會(huì)很麻煩。

這里作者提出來，利用責(zé)任鏈的設(shè)計(jì)模式，會(huì)使得寫出的算法擴(kuò)展性以及維護(hù)性更高。這里用到的思想就是，每個(gè)類只判斷一種類型。比如判斷是否是正數(shù)的類，判斷是否是小數(shù)的類，判斷是否是科學(xué)計(jì)數(shù)法的類，這樣每個(gè)類只關(guān)心自己的部分，出了問題很好排查，而且互不影響。

//每個(gè)類都實(shí)現(xiàn)這個(gè)接口
interface NumberValidate { 
    boolean validate(String s);
}
//定義一個(gè)抽象類，用來檢查一些基礎(chǔ)的操作，是否為空，去掉首尾空格，去掉 +/-
//doValidate 交給子類自己去實(shí)現(xiàn)
abstract class  NumberValidateTemplate implements NumberValidate{

    public boolean validate(String s)
    {
        if (checkStringEmpty(s))
        {
            return false;
        }

        s = checkAndProcessHeader(s);

        if (s.length() == 0)
        {
            return false;
        }

        return doValidate(s);
    }

    private boolean checkStringEmpty(String s)
    {
        if (s.equals(""))
        {
            return true;
        }

        return false;
    }

    private String checkAndProcessHeader(String value)
    {
        value = value.trim();

        if (value.startsWith("+") || value.startsWith("-"))
        {
            value = value.substring(1);
        }


        return value;
    }



    protected abstract boolean doValidate(String s);
}

//實(shí)現(xiàn) doValidate 判斷是否是整數(shù)
class IntegerValidate extends NumberValidateTemplate{

    protected boolean doValidate(String integer)
    {
        for (int i = 0; i < integer.length(); i++)
        {
            if(Character.isDigit(integer.charAt(i)) == false)
            {
                return false;
            }
        }

        return true;
    }
}
 
//實(shí)現(xiàn) doValidate 判斷是否是科學(xué)計(jì)數(shù)法
class SienceFormatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String s)
    {
        s = s.toLowerCase();
        int pos = s.indexOf("e");
        if (pos == -1)
        {
            return false;
        }

        if (s.length() == 1)
        {
            return false;
        }

        String first = s.substring(0, pos);
        String second = s.substring(pos+1, s.length());

        if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
        {
            return false;
        }


        return true;
    }

    private boolean validatePartBeforeE(String first)
    {
        if (first.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(first) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        NumberValidate floatValidate = new FloatValidate();
        if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkHeadAndEndForSpace(String part)
    {

        if (part.startsWith(" ") ||
            part.endsWith(" "))
        {
            return false;
        }

        return true;
    }

    private boolean validatePartAfterE(String second)
    {
        if (second.equals("") == true)
        {
            return false;
        }

        if (checkHeadAndEndForSpace(second) == false)
        {
            return false;
        }

        NumberValidate integerValidate = new IntegerValidate();
        if (integerValidate.validate(second) == false)
        {
            return false;
        }

        return true;
    }
}
//實(shí)現(xiàn) doValidate 判斷是否是小數(shù)
class FloatValidate extends NumberValidateTemplate{

    protected boolean doValidate(String floatVal)
    {
        int pos = floatVal.indexOf(".");
        if (pos == -1)
        {
            return false;
        }

        if (floatVal.length() == 1)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        String first = floatVal.substring(0, pos);
        String second = floatVal.substring(pos + 1, floatVal.length());

        if (checkFirstPart(first) == true && checkFirstPart(second) == true)
        {
            return true;
        }

        return false;
    }

    private boolean checkFirstPart(String first)
    {
        if (first.equals("") == false && checkPart(first) == false)
        {
            return false;
        }

        return true;
    }

    private boolean checkPart(String part)
    {
        if (Character.isDigit(part.charAt(0)) == false ||
            Character.isDigit(part.charAt(part.length() - 1)) == false)
        {
            return false;
        }

        NumberValidate nv = new IntegerValidate();
        if (nv.validate(part) == false)
        {
            return false;
        }

        return true;
    }
}
//定義一個(gè)執(zhí)行者，我們把之前實(shí)現(xiàn)的各個(gè)類加到一個(gè)數(shù)組里，然后依次調(diào)用
class NumberValidator implements NumberValidate {

    private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();

    public NumberValidator()
    {
        addValidators();
    }

    private  void addValidators()
    {
        NumberValidate nv = new IntegerValidate();
        validators.add(nv);

        nv = new FloatValidate();
        validators.add(nv);

        nv = new HexValidate();
        validators.add(nv);

        nv = new SienceFormatValidate();
        validators.add(nv);
    }

    @Override
    public boolean validate(String s)
    {
        for (NumberValidate nv : validators)
        {
            if (nv.validate(s) == true)
            {
                return true;
            }
        }

        return false;
    }


}
public boolean isNumber(String s) {
    NumberValidate nv = new NumberValidator(); 
    return nv.validate(s);
}

時(shí)間復(fù)雜度：

空間復(fù)雜度：

總

解法二中自動(dòng)機(jī)的應(yīng)用，會(huì)使得自己的思路更清晰。而解法三中，作者提出的對(duì)設(shè)計(jì)模式的應(yīng)用，使自己眼前一亮，雖然代碼變多了，但是維護(hù)性，擴(kuò)展性變的很強(qiáng)了。比如，題目新增了一種情況，"0x123" 16 進(jìn)制也算是合法數(shù)字。這樣的話，解法一和解法二就沒什么用了，完全得重新設(shè)計(jì)。但對(duì)于解法三，我們只需要新增一個(gè)類，專門判斷這種情況，然后加到執(zhí)行者的數(shù)組里就夠了，很棒！

更多詳細(xì)通俗題解詳見 leetcode.wang 。