[LeetCode]10.Regular Expression Matching
Given an input string (s) and a pattern (p), 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).
Note:
s could be empty and contains only lowercase letters a-z. p could be
empty and contains only lowercase letters a-z, and characters like .
or *. Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match
the entire string "aa". Example 2:
Input: s = "aa" p = "a" Output: true Explanation: ' ' means zero or
more of the precedeng element, 'a'. Therefore, by repeating 'a' once,
it becomes "aa". Example 3:
Input: s = "ab" p = "." Output: true Explanation: ". " means "zero or
more (*) of any character (.)". Example 4:
Input: s = "aab" p = "ca b" Output: true Explanation: c can be
repeated 0 times, a can be repeated 1 time. Therefore it matches
"aab". Example 5:
Input: s = "mississippi" p = "misis p*." Output: false
比較難的一道題
第一思路是雙指標解決，兩個指標分別匹配中移動，如果最後都指向隊尾，則匹配成功，利用貪心的思想，儘可能的往後匹配，最後判斷兩個串是否還有剩餘，但沒有考慮到一個情況，可能出現匹配多的情況，下面的情況就cover不了。
1111
1*1111
無法通過貪心解決的時候，就可以在無法決定的地方進行分支判斷，按照正向的就是遞迴的思想，不要忘了儲存狀態。
正向可以通過遞迴方式解決
public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0) return true;
if(p.length()>=2 && p.charAt(1)=='*'){
if(p.length()>=1 && s.length()>=1 && (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.')){
if(isMatch(s.substring(1),p)) return true;
}
if(isMatch(s,p.substring(2))) return true;
}
if(p.length()>=1 && s.length()>=1 && (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.')){
if(isMatch(s.substring(1),p.substring(1))) return true;
}
return false;
}
但是有一個比較明顯的優化點，重複計算了很多狀態，可以用一個二維陣列儲存狀態
int[][] dp;
public boolean isMatch(String s, String p) {
dp=new int[s.length()+1][p.length()+1];
dp[0][0]=1;
return ref(s,p);
}
public boolean ref(String s, String p) {
if(dp[s.length()][p.length()]!=0) return dp[s.length()][p.length()]==1;
boolean first=p.length()>=1 && s.length()>=1 && (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0));
if(p.length()>=2 && p.charAt(1)=='*'){
if(first){
if(ref(s.substring(1),p)){
dp[s.length()][p.length()]=1;
return true;
}
}
if(ref(s,p.substring(2))){
dp[s.length()][p.length()]=1;
return true;
}
}
if(first){
if(ref(s.substring(1),p.substring(1))){
dp[s.length()][p.length()]=1;
return true;
}
}
dp[s.length()][p.length()]=-1;
return false;
}