你的位置:首页 > Java教程

[Java教程]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   }

View Code

测试代码地址:

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:如有不正确或提高效率的方法,欢迎留言,谢谢!