校验数字的表达式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 数字：^[0-9]*$ n位的数字：^\d{n}$ 至少n位的数字：^\d{n,}$ m-n位的数字：^\d{m,n}$ 零和非零开头的数字：^(0|[1-9][0-9]*)$ 非零开头的最多带两位小数的数字：^([1-9][0-9]*)+(.[0-9]{1,2})?$ 带1-2位小数的正数或负数：^(\-)?\d+(\.\d{1,2})?$ 正数、负数、和小数：^(\-|\+)?\d+(\.\d+)?$ 有两位小数的正实数：^[0-9]+(.[0-9]{2})?$ 有1~3位小数的正实数：^[0-9]+(.[0-9]{1,3})?$ 非零的正整数：^[1-9]\d*$ 或 ^([1-9][0-9]*){1,3}$ 或 ^\+?[1-9][0-9]*$ 非零的负整数：^\-[1-9][]0-9"*$ 或 ^-[1-9]\d*$ 非负整数：^\d+$ 或 ^[1-9]\d*|0$ 非正整数：^-[1-9]\d*|0$ 或 ^((-\d+)|(0+))$ 非负浮点数：^\d+(\.\d+)?$ 或 ^[1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0$ 非正浮点数：^((-\d+(\.\d+)?)|(0+(\.0+)?))$ 或 ^(-([1-9]\d*\.\d*|0\.\d*[1-9]\d*))|0?\.0+|0$ 正浮点数：^[1-9]\d*\.\d*|0\.\d*[1-9]\d*$ 或 ^(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*))$ 负浮点数：^-([1-9]\d*\.\d*|0\.\d*[1-9]\d*)$ 或 ^(-(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*)))$ 浮点数：^(-?\d+)(\.\d+)?$ 或 ^-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)$
校验字符的表达式 1 2 3 4 5 6 7 8 9 10 11 12 汉字：^[\u4e00-\u9fa5]{0,}$ 英文和数字：^[A-Za-z0-9]+$ 或 ^[A-Za-z0-9]{4,40}$ 长度为3-20的所有字符：^.{3,20}$ 由26个英文字母组成的字符串：^[A-Za-z]+$ 由26个大写英文字母组成的字符串：^[A-Z]+$ 由26个小写英文字母组成的字符串：^[a-z]+$ 由数字和26个英文字母组成的字符串：^[A-Za-z0-9]+$ 由数字、26个英文字母或者下划线组成的字符串：^\w+$ 或 ^\w{3,20}$ 中文、英文、数字包括下划线：^[\u4E00-\u9FA5A-Za-z0-9_]+$ 中文、英文、数字但不包括下划线等符号：^[\u4E00-\u9FA5A-Za-z0-9]+$ 或 ^[\u4E00-\u9FA5A-Za-z0-9]{2,20}$ 可以输入含有^%&',;=?$\"等字符：[^%&',;=?$\x22]+ 禁止输入含有~的字符：[^~\x22]+
特殊需求表达式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Email地址：^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$ 域名：[a-zA-Z0-9][-a-zA-Z0-9]{0,62}(/.[a-zA-Z0-9][-a-zA-Z0-9]{0,62})+/.? InternetURL：[a-zA-z]+://[^\s]* 或 ^http://([\w-]+\.)+[\w-]+(/[\w-./?%&=]*)?$ 手机号码：^(13[0-9]|14[0-9]|15[0-9]|16[0-9]|17[0-9]|18[0-9]|19[0-9])\d{8}$ (由于工信部放号段不定时，所以建议使用泛解析 ^([1][3,4,5,6,7,8,9])\d{9}$) 电话号码("XXX-XXXXXXX"、"XXXX-XXXXXXXX"、"XXX-XXXXXXX"、"XXX-XXXXXXXX"、"XXXXXXX"和"XXXXXXXX)：^(\(\d{3,4}-)|\d{3.4}-)?\d{7,8}$ 国内电话号码(0511-4405222、021-87888822)：\d{3}-\d{8}|\d{4}-\d{7} 18位身份证号码(数字、字母x结尾)：^((\d{18})|([0-9x]{18})|([0-9X]{18}))$ 帐号是否合法(字母开头，允许5-16字节，允许字母数字下划线)：^[a-zA-Z][a-zA-Z0-9_]{4,15}$ 密码(以字母开头，长度在6~18之间，只能包含字母、数字和下划线)：^[a-zA-Z]\w{5,17}$ 强密码(必须包含大小写字母和数字的组合，不能使用特殊字符，长度在8-10之间)：^(?=.*\d)(?=.*[a-z])(?=.*[A-Z]).{8,10}$ 日期格式：^\d{4}-\d{1,2}-\d{1,2} 一年的12个月(01～09和1～12)：^(0?[1-9]|1[0-2])$ 一个月的31天(01～09和1～31)：^((0?[1-9])|((1|2)[0-9])|30|31)$ 钱的输入格式： 1.有四种钱的表示形式我们可以接受:"10000.00" 和 "10,000.00", 和没有 "分" 的 "10000" 和 "10,000"：^[1-9][0-9]*$ 2.这表示任意一个不以0开头的数字,但是,这也意味着一个字符"0"不通过,所以我们采用下面的形式：^(0|[1-9][0-9]*)$ 3.一个0或者一个不以0开头的数字.我们还可以允许开头有一个负号：^(0|-?[1-9][0-9]*)$ 4.这表示一个0或者一个可能为负的开头不为0的数字.让用户以0开头好了.把负号的也去掉,因为钱总不能是负的吧.下面我们要加的是说明可能的小数部分：^[0-9]+(.[0-9]+)?$ 5.必须说明的是,小数点后面至少应该有1位数,所以"10."是不通过的,但是 "10" 和 "10.2" 是通过的：^[0-9]+(.[0-9]{2})?$ 6.这样我们规定小数点后面必须有两位,如果你认为太苛刻了,可以这样：^[0-9]+(.[0-9]{1,2})?$ 7.这样就允许用户只写一位小数.下面我们该考虑数字中的逗号了,我们可以这样：^[0-9]{1,3}(,[0-9]{3})*(.[0-9]{1,2})?$ 8.1到3个数字,后面跟着任意个 逗号+3个数字,逗号成为可选,而不是必须：^([0-9]+|[0-9]{1,3}(,[0-9]{3})*)(.[0-9]{1,2})?$ 备注：这就是最终结果了,别忘了"+"可以用"*"替代如果你觉得空字符串也可以接受的话(奇怪,为什么?)最后,别忘了在用函数时去掉去掉那个反斜杠,一般的错误都在这里 xml文件：^([a-zA-Z]+-?)+[a-zA-Z0-9]+\\.[x|X][m|M][l|L]$ 中文字符的正则表达式：[\u4e00-\u9fa5] 双字节字符：[^\x00-\xff] (包括汉字在内，可以用来计算字符串的长度(一个双字节字符长度计2，ASCII字符计1)) 空白行的正则表达式：\n\s*\r (可以用来删除空白行) HTML标记的正则表达式：<(\S*?)[^>]*>.*?</\1>|<.*? /> (网上流传的版本太糟糕，上面这个也仅仅能部分，对于复杂的嵌套标记依旧无能为力) 首尾空白字符的正则表达式：^\s*|\s*$或(^\s*)|(\s*$) (可以用来删除行首行尾的空白字符(包括空格、制表符、换页符等等)，非常有用的表达式) 腾讯QQ号：[1-9][0-9]{4,} (腾讯QQ号从10000开始) 中国邮政编码：[1-9]\d{5}(?!\d) (中国邮政编码为6位数字) IP地址：\d+\.\d+\.\d+\.\d+ (提取IP地址时有用) IP地址：((?:(?:25[0-5]|2[0-4]\\d|[01]?\\d?\\d)\\.){3}(?:25[0-5]|2[0-4]\\d|[01]?\\d?\\d))
实现 正则表达式是一个非常强力的工具，本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配」就要求我们实现一个简单的正则匹配算法，包括「.」通配符和「*」通配符。
这两个通配符是最常用的，其中点号「.」可以匹配任意一个字符，星号「*」可以让之前的那个字符重复任意次数（包括 0 次）。
比如说模式串.a*b就可以匹配文本zaaab，也可以匹配cb；模式串a..b可以匹配文本amnb；而模式串.*就比较牛逼了，它可以匹配任何文本。
题目会给我们输入两个字符串s和p，s代表文本，p代表模式串，请你判断模式串p是否可以匹配文本s。我们可以假设模式串只包含小写字母和上述两种通配符且一定合法，不会出现*a或者b**这种不合法的模式串，
函数签名如下：
1 bool isMatch(string s, string p);
对于我们将要实现的这个正则表达式，难点在那里呢？
点号通配符其实很好实现，s中的任何字符，只要遇到.通配符，无脑匹配就完事了。主要是这个星号通配符不好实现，一旦遇到*通配符，前面的那个字符可以选择重复一次，可以重复多次，也可以一次都不出现，这该怎么办？
对于这个问题，答案很简单，对于所有可能出现的情况，全部穷举一遍，只要有一种情况可以完成匹配，就认为p可以匹配s。那么一旦涉及两个字符串的穷举，我们就应该条件反射地想到动态规划的技巧了。
思路分析 我们先脑补一下，s和p相互匹配的过程大致是，两个指针i, j分别在s和p上移动，如果最后两个指针都能移动到字符串的末尾，那么久匹配成功，反之则匹配失败。
正则表达算法问题只需要把住一个基本点：看两个字符是否匹配，一切逻辑围绕匹配/不匹配两种情况展开即可。
如果不考虑*通配符，面对两个待匹配字符s[i]和p[j]，我们唯一能做的就是看他俩是否匹配：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 bool isMatch (string s, string p) int i = 0 , j = 0 ; while (i < s.size () && j < p.size ()) { if (s[i] == p[j] || p[j] == '.' ) { i++; j++; } else { return false ; } } return i == j; }
那么考虑一下，如果加入*通配符，局面就会稍微复杂一些，不过只要分情况来分析，也不难理解。
当p[j + 1]为*通配符时，我们分情况讨论下：
如果匹配，即s[i] == p[j]，那么有两种情况：
p[j]有可能会匹配多个字符，比如s = aaa, p = a*，那么p[0]会通过*匹配 3 个字符a。
p[i]也有可能匹配 0 个字符，比如s = aa, p = a*aa，由于后面的字符可以匹配s，所以p[0]只能匹配 0 次。
如果不匹配，即s[i] != p[j]，只有一种情况：
p[j]只能匹配 0 次，然后看下一个字符是否能和s[i]匹配。比如说s = aa, p = b*aa，此时p[0]只能匹配 0 次。
综上，可以把之前的代码针对*通配符进行一下改造：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 if (s[i] == p[j] || p[j] == '.' ) { if (j < p.size () - 1 && p[j + 1 ] == '*' ) { } else { i++; j++; } } else { if (j < p.size () - 1 && p[j + 1 ] == '*' ) { } else { return false ; } }
整体的思路已经很清晰了，但现在的问题是，遇到*通配符时，到底应该匹配 0 次还是匹配多次？多次是几次？
你看，这就是一个做「选择」的问题，要把所有可能的选择都穷举一遍才能得出结果。动态规划算法的核心就是「状态」和「选择」，「状态」无非就是i和j两个指针的位置，「选择」就是p[j]选择匹配几个字符。
动态规划解法 根据「状态」，我们可以定义一个dp函数：
1 bool dp(string& s, int i, string& p, int j);
dp函数的定义如下：若dp(s,i,p,j) = true，则表示s[i..]可以匹配p[j..]；若dp(s,i,p,j) = false，则表示s[i..]无法匹配p[j..]。根据这个定义，我们想要的答案就是i = 0,j = 0时dp函数的结果，所以可以这样使用这个dp函数：
1 2 3 bool isMatch(string s, string p) { // 指针 i，j 从索引 0 开始移动 return dp(s, 0, p, 0);
可以根据之前的代码写出dp函数的主要逻辑：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 bool dp (string& s, int i, string& p, int j) if (s[i] == p[j] || p[j] == '.' ) { if (j < p.size () - 1 && p[j + 1 ] == '*' ) { return dp (s, i, p, j + 2 ) || dp (s, i + 1 , p, j); } else { return dp (s, i + 1 , p, j + 1 ); } } else { if (j < p.size () - 1 && p[j + 1 ] == '*' ) { return dp (s, i, p, j + 2 ); } else { return false ; } } }
根据dp函数的定义，这几种情况都很好解释：
通配符匹配 0 次或多次
将j加 2，i不变，含义就是直接跳过p[j]和之后的通配符，即通配符匹配 0 次：
将i加 1，j不变，含义就是p[j]匹配了s[i]，但p[j]还可以继续匹配，即通配符匹配多次的情况：
两种情况只要有一种可以完成匹配即可，所以对上面两种情况求或运算。
常规匹配 1 次
由于这个条件分支是无*的常规匹配，那么如果s[i] == p[j]，就是i和j分别加一：
通配符匹配 0 次
如果没有*通配符，也无法匹配，那只能说明匹配失败了：
看图理解应该很容易了，现在可以思考一下dp函数的 base case：
一个 base case 是j == p.size()时，按照dp函数的定义，这意味着模式串p已经被匹配完了，那么应该看看文本串s匹配到哪里了，如果s也恰好被匹配完，则说明匹配成功：
1 2 3 if (j == p.size ()) { return i == s.size (); }
另一个 base case 是i == s.size()时，按照dp函数的定义，这种情况意味着文本串s已经全部被匹配了，那么是不是只要简单地检查一下p是否也匹配完就行了呢？
1 2 3 4 if (i == s.size ()) { return j == p.size (); }
这是不正确的，此时并不能根据j是否等于p.size()来判断是否完成匹配，只要p[j..]能够匹配空串，就可以算完成匹配。比如说s = “a”, p = “abc “，当i走到s末尾的时候，j并没有走到p的末尾，但是p依然可以匹配s。所以我们可以写出如下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int m = s.size (), n = p.size ();if (i == s.size ()) { if ((n - j) % 2 == 1 ) { return false ; } for (; j + 1 < p.size (); j += 2 ) { if (p[j + 1 ] != '*' ) { return false ; } } return true ; }
根据以上思路，就可以写出完整的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 bool dp (string& s, int i, string& p, int j) int m = s.size (), n = p.size (); if (j == n) { return i == m; } if (i == m) { if ((n - j) % 2 == 1 ) { return false ; } for (; j + 1 < n; j += 2 ) { if (p[j + 1 ] != '*' ) { return false ; } } return true ; } string key = to_string (i) + "," + to_string (j); if (memo.count (key)) return memo[key]; bool res = false ; if (s[i] == p[j] || p[j] == '.' ) { if (j < n - 1 && p[j + 1 ] == '*' ) { res = dp (s, i, p, j + 2 ) || dp (s, i + 1 , p, j); } else { res = dp (s, i + 1 , p, j + 1 ); } } else { if (j < n - 1 && p[j + 1 ] == '*' ) { res = dp (s, i, p, j + 2 ); } else { res = false ; } } memo[key] = res; return res; }
代码中用了一个哈希表memo消除重叠子问题，因为正则表达算法的递归框架如下：
1 2 3 4 5 bool dp (string& s, int i, string& p, int j) dp (s, i, p, j + 2 ); dp (s, i + 1 , p, j); dp (s, i + 1 , p, j + 1 ); }
那么，如果让你从dp(s, i, p, j)得到dp(s, i+2, p, j+2)，至少有两条路径：1 -> 2 -> 2和3 -> 3，那么就说明(i+2, j+2)这个状态存在重复，这就说明存在重叠子问题。
动态规划的时间复杂度为「状态的总数」*「每次递归花费的时间」，本题中状态的总数当然就是i和j的组合，也就是M * N（M为s的长度，N为p的长度）；递归函数dp中没有循环（base case 中的不考虑，因为 base case 的触发次数有限），所以一次递归花费的时间为常数。二者相乘，总的时间复杂度为O(MN)。空间复杂度很简单，就是备忘录memo的大小，即O(MN)。