首页 > 代码库 > No.010：Regular Expression Matching
No.010：Regular Expression Matching
题目：
Implement regular expression matching with support for ‘.‘ and ‘*‘.
‘.‘ Matches any single character.
‘*‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Some Examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("aab", ".*a") → false
isMatch("aab", ".*ab") → true
官方难度：
Hard
翻译：
实现字符串正则表达式匹配，支持特殊符号"."和"*"。
"."可以匹配任意单个字符。
"*"可以匹配0个或更多的在*之前的字符。
匹配算法应该能够匹配以下所有的例子，而非部分。
例子：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("aab", ".*a") → false
isMatch("aab", ".*ab") → true
思路：
1.只考虑正则表达式的匹配字符串只包括"*"和"."两种特殊符号，其余特殊符号（包括括号）不在考虑范围之内。
2.以待解析的字符串长度为基准，开始遍历。
3.如果遍历途中，出现待解析字符串尚存，而正则字符串不在了，或反之的情况，返回失败。
4.从第一个字符开始，不考虑特殊符号的情况下，若匹配，进行待解析和正则字符串的下一个匹配工作。
5.特殊字符串"."单独出现的情况，当次匹配直接通过。
6.特殊字符串"*"单独出现的情况，计算"*"上一个字符在待解析字符串中的长度，待解析字符串在下次计算中会跳过那个长度（包括0的情况）。
7.特殊字符串".*"组合出现的情况，这种情况可以匹配，任意长，任意内容的字符串。如".*"可以匹配"abhsjksdhak"，".*a"可以匹配"dhaudhjoaidhaida"但是不能匹配"bdab"。
8.出现7的情况，需要考虑，遍历待解析字符串剩余部分，能否匹配正则字符串".*"之后的部分。如"ab.*c.d"和"abctucid"，需要依次检查"ctucid"是否匹配"c.d"，"tucid"是否匹配"c.d"，直至"d"是否匹配"c.d"，只要存在一次匹配成功，就返回true。
解题中可能遇到的困难：
1.注意待解析字符串遍历完毕之后，需要对正则字符串的长度做检验。
2.".*"的处理的方法，是和任意字符+"*"的方法写在一起的，返回值是一个长度，注意处理结束返回一个特殊值，不要影响其他操作。
解题代码：
1 private static boolean method(String str, String regularStr) { 2 String strWithoutHead = str; 3 String regularStrWithoutHead = regularStr; 4 int alreadyMatchedLength = 0; 5 // 待处理的正则字符串 6 String regularStrToDeal = null; 7 int strLengthToReduce; 8 while (alreadyMatchedLength < str.length()) { 9 // 因为退出条件是解析完成字符串长度=原长度，10 // 所以一次循环完成时，要判断一下，正则的长度够不够11 if (regularStrWithoutHead.length() == 0) {12 return false;13 }14 if (regularStrWithoutHead.length() > 1 && regularStrWithoutHead.substring(1, 2).equals("*")) {15 // 第二个数是"*"情况16 regularStrToDeal = regularStrWithoutHead.substring(0, 2);17 // 考虑到".*"的情况，把剩余整个正则和待处理字符串传进去18 strLengthToReduce = matchStarLength(strWithoutHead, regularStrWithoutHead);19 // ".*"的特殊处理，因为有递归，这里就是一个出口20 if (strLengthToReduce == -1) {21 return true;22 } else if (strLengthToReduce == -2) {23 return false;24 }25 } else {26 // 单个匹配情况27 regularStrToDeal = regularStrWithoutHead.substring(0, 1);28 if (!singleStringMatch(strWithoutHead.substring(0, 1), regularStrToDeal)) {29 return false;30 }31 strLengthToReduce = 1;32 }33 // 增加已处理的字符串长度34 alreadyMatchedLength += strLengthToReduce;35 // 去头36 strWithoutHead = str.substring(alreadyMatchedLength);37 regularStrWithoutHead = regularStrWithoutHead.substring(regularStrToDeal.length());38 }39 // 待解析完成，但正则还有40 if (regularStrWithoutHead.length() > 0) {41 return false;42 }43 return true;44 }45 46 // 单个字符匹配问题47 private static boolean singleStringMatch(String str, String regularStr) {48 // 特殊符号"."处理49 if (regularStr.equals(".")) {50 return true;51 } else if (str.equals(regularStr)) {52 return true;53 }54 return false;55 }56 57 // 由于"*"一定会匹配成功，返回原字符串的匹配长度58 // str不是原字符串，是"*"开始匹配的第一个位置59 private static int matchStarLength(String str, String regularString) {60 int length = 0;61 if (regularString.substring(0, 1).equals(".")) {62 // 最最最烦的一点：".*"处理63 // 先把对应的正则字符串去掉".*"64 String regularRemain = regularString.substring(2);65 // ".*"之后不跟，匹配一切66 if (regularRemain.equals("")) {67 // 返回剩下的字符串长度68 return str.length();69 }70 // 用余下的东西递归71 for (int i = 0; i < str.length(); i++) {72 String remain = str.substring(i);73 // 开始递归74 if (method(remain, regularRemain)) {75 // 只要出现true，直接整个都可以匹配76 return -1;77 }78 }79 // 余下的都不成功，表示整个不匹配80 return -2;81 } else {82 // 正常字符+"*"83 String regularInUse = regularString.substring(0, 1);84 for (int i = 0; i < str.length(); i++) {85 if (regularInUse.equals(str.substring(i, i + 1))) {86 length++;87 } else {88 break;89 }90 }91 }92 return length;93 }
测试代码地址：
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/hard/Q010.java
LeetCode题目地址：
https://leetcode.com/problems/regular-expression-matching/
PS：写完才发现，不使用循环待解析字符串，直接对剩余的字符串使用递归，可能是一种更好的思想。
PPS：如有不正确或提高效率的方法，欢迎留言，谢谢！
No.010：Regular Expression Matching