Leetcode: Valid Number的三种解法

前言

Leetcode做到Valid Number这道题, 看到 Leetcode题目分类 中说这道题难度为二级(总共五级), 还以为这道题真的很简单。。。真是坑了大爹了。

仔细总结了下, 这道题大概有三种解法:

题目

https://oj.leetcode.com/problems/valid-number/

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. 

You should gather all requirements up front before implementing one.

解法一:

这种方法用正则表达式来解决, 算是最简单优雅的一种方法了。

class Solution2
{
public:
    bool isNumber(const char *s) 
    {   
<span style="white-space:pre">  </span>regex re("( *)[+-]?(\\d+|\\d+\\.\\d*|\\d*\\.\\d+)([eE][+-]?\\d+)?");

        if (regex_match(s, re))
            return true;
        else
            return false;
    }   

};

不过截止到发文章, g++ 4.8.2貌似还是没有完全支持正则表达式, 所以这段代码编译会报错。

但是如果用Java或Python的话, 应该没问题了。

另一方面, 面试的时候恐怕不会允许简简单单的用正则表达式来解决这个问题, 所以还要掌握其他方法。

解法二:

2.1 DFA

第二种方法用DFA来解决这个问题, 用到了了编译原理中的tokenizer那部分的思想。

这种方法写代码之前要先画出图来才行,我画的如下:

SouthEast

画的有点乱, 不过领会精神就好。 :)

代码如下:

class Solution2_1
{
public:
public:
    bool isNumber(const char *s)
    {
        int state = 0;

        while (1)
        {
            switch (state)
            {
                case 0:
                    if (*s == ' ')
                        state = 0;
                    else if (*s == '+' || *s == '-')
                        state = 1;
                    else if (isdigit(*s))
                        state = 2;
                    else if (*s == '.')
                        state = 9;
                    else 
                        state = 8;
                    break;

                case 1:
                    if (isdigit(*s))
                        state = 2;
                    else if (*s == '.')
                        state = 9;
                    else
                        state = 8;
                    break;

                case 2:
                    if (isdigit(*s))
                        state = 2;
                    else if (*s == '.')
                        state = 3;
                    else if (*s == '\0')
                        state = 7;
                    else if (*s == ' ')
                        state = 10;
                    else if (*s == 'e' || *s == 'E')
                        state = 5;
                    else
                        state = 8;
                    break;

                case 3:
                    if (isdigit(*s))
                        state = 4;
                    else if (*s == '\0')
                        state = 7;
                    else if (*s == ' ')
                        state = 10;
                    else if (*s == 'e' || *s == 'E')
                        state = 5;
                    else
                        state = 8;
                    break;

                case 4:
                    if (isdigit(*s))
                        state = 4;
                    else if (*s == 'e' || *s == 'E')
                        state = 5;
                    else if (*s == '\0')
                        state = 7;
                    else if (*s == ' ')
                        state = 10;
                    else
                        state = 8;
                    break;

                case 5:
                    if (isdigit(*s))
                        state = 6;
                    else if (*s == '+' || *s == '-')
                        state = 11;
                    else
                        state = 8;
                    break;

                case 6:
                    if (isdigit(*s))
                        state = 6;
                    else if (*s == ' ')
                        state = 6;
                    else if (*s == '\0')
                        state = 7;
                    else if (*s == ' ')
                        state = 10;
                    else
                        state = 8;
                    break;

                case 7:
                    return true;

                case 8:
                    return false;

                case 9:
                    if (isdigit(*s))
                        state = 4;
                    else
                        state = 8;
                    break;

                case 10:
                    if (*s == '\0')
                        state = 7;
                    else if (*s == ' ')
                        state = 10;
                    else
                        state = 8;
                    break;
                case 11:
                    if (isdigit(*s))
                        state = 6;
                    else 
                        state = 8;
                    break;
            }
            s++;
        }
    }
};

这段代码可能开起来有点长, 不过只要弄明白了那张状态转换图很容易明白的。

2.2 DFA改进版

上面这段代码可能有点长, 所以用二维数组对其进行改进:

SouthEast 1

代码如下:

class Solution2_2
{
public:
    bool isNumber(const char *s)
    {
        int state = 0;
        int translate[][7] =
        {
            0, 1, 2, 8, 9, 8, 8,    //0
            8, 8, 2, 8, 9, 8, 8,    //1
            10, 8, 2, 5, 3, 7, 8,   //2
            10, 8, 4, 5, 8, 7, 8,   //3
            10, 8, 4, 5, 8, 7, 8,   //4
            8, 11, 6, 8, 8, 8, 8,   //5
            10, 8, 6, 8, 8, 7, 8,   //6
            7, 7, 7, 7, 7, 7, 7,    //7
            8, 8, 8, 8, 8, 8, 8,    //8
            8, 8, 4, 8, 8, 8, 8,    //9
            10, 8, 8, 8, 8, 7, 8,   //10
            8, 8, 6, 8, 8, 8, 8     //11
        };

        int type;
        while (1)
        {
            if (*s == ' ')
                type = 0;
            else if (*s == '+' || *s == '-')
                type = 1;
            else if (isdigit(*s))
                type = 2;
            else if (*s == 'e' || *s == 'E')
                type = 3;
            else if (*s == '.')
                type = 4;
            else if (*s == '\0')
                type = 5;
            else 
                type = 6;

            state = translate[state][type];

            if (state == 7)
                return true;
            else if (state == 8)
                return false;

            s++;
        }
    }
};

解法三:

用多个flag来标识现在的状态, 可读性比较差, 不推荐。

class Solution3 {
public:
    bool isNumber(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        if (s == NULL)
             return false;

         while(isspace(*s))
             s++;

         if (*s == '+' || *s == '-')
             s++;

         bool eAppear = false;
         bool dotAppear = false;
         bool firstPart = false;
         bool secondPart = false;
         bool spaceAppear = false;
         while(*s != '\0')
         {
             if (*s == '.')
             {
                 if (dotAppear || eAppear || spaceAppear)
                     return false;
                 else
                     dotAppear = true;
             }
             else if (*s == 'e' || *s == 'E')
             {
                 if (eAppear || !firstPart || spaceAppear)
                     return false;
                 else
                     eAppear = true;
             }
             else if (isdigit(*s))
             {
                 if (spaceAppear)
                     return false;

                 if (!eAppear)
                     firstPart = true;
                 else
                     secondPart = true;
             }
             else if (*s == '+' || *s == '-')   // behind of e/E
             {
                 if (spaceAppear)
                     return false;

                 if (!eAppear || !(*(s-1) == 'e' || *(s-1) == 'E'))
                     return false;
             }
             else if (isspace(*s))
                 spaceAppear = true;
             else
                 return false;

             s++;            
         }

         if (!firstPart) {
             return false;
         }  else if (eAppear && !secondPart) {
             return false;
         } 
         return true;  
    }
};

源码:

Github上的源码

参考:

Leetcode 150题目终结贴 - Valid Number

【leetcode】Valid Number

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38487239