专栏首页计算机视觉与深度学习基础Leetcode 65 Valid Number DFA有限状态机

Leetcode 65 Valid Number DFA有限状态机

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.

Update (2015-02-10):

The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

判断数字的合法性

刚开始是把它作为一道细节较多的模拟题做的,通过后去discuss看了一下,果然有优美的解答!

用有限状态机DFA解决,将每一位看成一种状态转移条件,每次读取的一位,就根据转移矩阵进行状态转移,若转移到不合法的状态则返回false。

思路简单优美,不用考虑多余的细节问题,刷了这么多leetcode,这题真的眼前一亮!

具体的状态说明可以看这篇博客

class Solution {
public:
    bool isNumber(string s) {
        int mp[9][6]={
            {-1,  0,  1,  2, -1,  3},
            {-1, -1, -1,  2, -1,  3},
            {-1, -1, -1, -1, -1,  4},
            {-1,  5, -1,  4,  6,  3},
            {-1,  5, -1, -1,  6,  4},
            {-1,  5, -1, -1, -1, -1},
            {-1, -1,  7, -1, -1,  8},
            {-1, -1, -1, -1, -1,  8},
            {-1,  5, -1, -1, -1,  8}
        };
        int now=0;
        for(int i=0;i<s.size();i++)
        {
            switch(s[i])
            {
                case '-': now=mp[now][2];break;
                case '+': now=mp[now][2];break;
                case ' ': now=mp[now][1];break;
                case '.': now=mp[now][3];break;
                case 'e': now=mp[now][4];break;
                case 'E': now=mp[now][4];break;
                default: 
                {
                    if(s[i]>='0' && s[i]<='9')
                        now=mp[now][5];
                    else
                        now=mp[now][0];
                }
            }
            if(now==-1) return false;
        }
        return now==3 || now==4 || now==5 || now==8 ;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 77 Combinations

    Given two integers n and k, return all possible combinations of k numbers out o...

    triplebee
  • leetcode 6 ZigZag Conversion

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of...

    triplebee
  • Leetcode 212 Word Search II 字典树 + 回溯

    Given a 2D board and a list of words from the dictionary, find all words in the...

    triplebee
  • javascript_data

    机器学习和大数据挖掘
  • P1996 约瑟夫问题

    题目背景 约瑟夫是一个无聊的人!!! 题目描述 n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出...

    attack
  • 一日一技:实现函数调用结果的 LRU 缓存

    在工程项目中,可能有一些函数调用耗时很长,但是又需要反复多次调用,并且每次调用时,相同的参数得到的结果都是相同的。在这种情况下,我们可能会使用变量或者列表来存放...

    青南
  • Struts2之类型转换器

    爱撒谎的男孩
  • 使用Nacos做为SpringCloud的注册中心

    【转载请注明出处】:https://cloud.tencent.com/developer/article/1642606

    后端老鸟
  • Art of Android Development Reading Notes 5

    《Android开发艺术探索》读书笔记 (5) 第5章 理解RemoteViews

    宅男潇涧
  • 策略模式+元注解方式替代大量if else写法

    策略模式:定义一系列算法,然后将每一个算法封装起来,并将它们可以互相替换。也就是将一系列算法封装到一系列策略类里面。策略模式是一种对象行为型模式。策略模式符合“...

    SmileNicky

扫码关注云+社区

领取腾讯云代金券