leetcode 10.Regular Expression Matching(正则表达式匹配) 解题

isMatch("aab","c*a*b") → true

这题难度为hard,最主要的实现方法是用递归方法，先判断边界条件，然后再判断p字符串中第二个字符时候为*，分情况讨论。

具体代码和注释如下：

public class Solution {
    public boolean isMatch(String s,String p) {
        if (s == null)
            return p == null;
        if (p == null)
            return s == null;
 
        int lenS = s.length();
        int lenP = p.length();

        if (lenP == 0)
            return lenS == 0;
        
        if(lenP == 1){
            if(lenS == 1){
                if(p.equals(".") || p.equals(s)){
                	return true;
                }
            }
            return false;
        }
        //字符后为*
        if(p.charAt(1) == '*'){
        	  int i = 0;
        	  while(s.length() > 0 && isEquals(s.charAt(0),p.charAt(0))){
        		  //如果截取p的两位后还能匹配，则返回true,如果不能,s截取前i位后与p重新匹配
        		  if(isMatch(s,p.substring(2)))
                      return true;
        		  s = s.substring(1);
        	  }
        	  return isMatch(s.substring(i),p.substring(2));
        }
        //字符后不为*
        else{
        	if(lenS > 0 && isEquals(s.charAt(0),p.charAt(0))){
        		return isMatch(s.substring(1),p.substring(1));
        	}
        	else{
        		return false;
        	}
        }
    }
    
    //判断是否相等
    public static boolean isEquals(char x,char y){
        if(x == y || y == '.'){
            return true;
        }
        return false;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!