검 지 Offer - 16 - 정규 표현 식 일치
20922 단어 검 지 Offer 문제 풀이
/**
*
* @Description
*/
public class Test17 {
//
public boolean isMatch1(String s, String p) {
return s.matches(p);
}
//
public boolean isMatch2(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m ; j++) {
//
if (j == 0){
dp[i][j] = i == 0;
}else {
//
if (p.charAt(j - 1) != '*'){
if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j -1) == '.')){
dp[i][j] = dp[i - 1][j - 1];
}
}else {
// * ,
//
if (j >= 2) {
dp[i][j] |= dp[i][j - 2];
}
//
if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
dp[i][j] |= dp[i - 1][j];
}
}
}
}
}
return dp[n][m];
}
// offer
private boolean isMatch3(String s, String p){
if (s == null || p == null){
return false;
}
char[] strs = s.toCharArray();
char[] pats = p.toCharArray();
return matchCore(strs, 0, pats, 0);
}
private boolean matchCore(char[] strs, int indexOfStrs, char[] pats, int indexOfPats) {
if (indexOfStrs == strs.length && indexOfPats ==pats.length){
return true;
}
if (indexOfStrs < strs.length && indexOfPats == pats.length){
return false;
}
if (indexOfPats + 1 < pats.length && pats[indexOfPats + 1] == '*'){
if ((indexOfStrs < strs.length && pats[indexOfPats] == '.') || (indexOfStrs < strs.length && pats[indexOfPats] == strs[indexOfStrs])){
return matchCore(strs,indexOfStrs,pats,indexOfPats+2) ||
matchCore(strs,indexOfStrs + 1,pats,indexOfPats) ||
matchCore(strs,indexOfStrs + 1,pats,indexOfPats + 2);
}else{
// , ‘*’
matchCore(strs,indexOfStrs,pats,indexOfPats+2);
}
}
if (indexOfStrs < strs.length && (pats[indexOfPats] == strs[indexOfStrs] || pats[indexOfPats] == '.'))
return matchCore(strs, indexOfStrs + 1, pats, indexOfPats + 1);
return false;
}
public static void main(String[] args) {
System.out.println(new Test17().isMatch2("ab", ".*"));
}
}