# LeetCode[动态规划] - #10 Regular Expression Matching

'.'匹配任意单字符。

'*'匹配任何0个或多个之前元素。

boolean isMatch(String /* string to check */ s, String /* patterns */ p)

isMatch("aa", "a") → false

isMatch("aa", "aa") → true

isMatch("aaa", "aa") → false

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

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

Java - 340 ms

```// Dynamic Programming Solution
public boolean isMatch(String /* string to check */ s, String /* patterns */ p) {
boolean[] match = new boolean[s.length()+1];
for(int i=0; i<match.length; i++){
match[i] = false;
}
match[s.length()] = true;
for(int i=p.length()-1; i>=0; i--){
if(p.charAt(i)=='*'){
for(int j=s.length()-1; j>=0; j--){
match[j] = match[j]||match[j+1]&&(p.charAt(i-1)=='.'||p.charAt(i-1)==s.charAt(j));
}
i--;
}else {
for(int j=0; j<s.length(); j++){
match[j] = match[j+1]&&(p.charAt(i)=='.'||p.charAt(i)==s.charAt(j));
}
match[s.length()] = false;
}
}
return match[0];
}```

LeetCode[动态规划] - #10 Regular Expression Matching

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊