Regular Expression Matching, Leetcode 解题笔记

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

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

又是一道5星级难度的题,开始完全没有思路,感觉各种分支情况太多,很混乱,后来参考了这个前辈的代码:http://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/,恍然大悟,对其思路五体投地。

链接中的源代码很难懂,为了更清楚的展示代码思路,我对他精简过的代码做了修改并添加了注释,使其看起来更直观,让人更易懂,方便以后复习,也符合KISS原则。

主要思路是递归,每次比较s和p的第一个字符,难点主要集中在对’*’的处理,几种分支情况要想清楚。
主要有两个case:
case 1:p的第二个字符不是’*’,这种是简单情况。
case 2:p的第二个字符是’*’,这种情况相对复杂。

对于每次对比,还要注意p的第一个字符是否为’.’,如果是,则match,继续比较后面的。

public class Solution {
    public boolean isMatch(String s, String p) {
        //base case
        if(p.length() == 0){
            return s.length() == 0;
        }
        
        //special case
        if(p.length() == 1){
            
            //if the length of s is 0, return false
            if(s.length() < 1){
                return false;
            }
            
            /*if the first char of s and the first char of p is not the same, 
            and the char of p is not '.', return false */
            else if((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')){
                return false;
            }
            
            //otherwise, compare the rest of the string of s and p.
            else{
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        
        //case 1: when the second char of p is not '*', easy case.
        if(p.charAt(1) != '*'){
            if(s.length() < 1){
                return false;
            }
            if((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')){
                return false;
            }
            else{
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        
        //case 2: when the second char of p is '*', complex case.
        else{
            
            //when the '*' stands for 0 preceding element
            if(isMatch(s, p.substring(2))){
                return true;
            }
            
            /*when the '*' stands for 1 or more preceding element,
            try every possible number*/
            int i = 0;
            while(i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')){
                if(isMatch(s.substring(i+1), p.substring(2))){
                    return true;
                }
                i++;
            }
            return false;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s