Given a regular expression with characters a-z, ' * ', ' . '
the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
* can only delete the character before it, but * can be skipped. "a*" is "a" or is an empty string ""
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;
翻译：给你一个使用字符a-z,'*','.'组成的规则字符串，字符串中'*'能够删除它前面一个字符，'.'能够匹配任何字符，'*'总是出现在a-z字符之后，任务是根据上述规则判断该字符串是否与一个a-z组成的字符串匹配。
另外：'*'只能够删除它之前的那个字符，或者被忽略。
分析：字符虽然不多，但判断条件较为繁琐，分不同情况，递归处理。
public class MatchStr {
/**
* 给你一个使用字符a-z,'*','.'组成的规则字符串，
* 字符串中'*'能够删除它前面一个字符或者被忽略，'.'能够匹配任何字符，'*'总是出现在a-z字符之后，
* 任务是根据上述规则，比较两个字符串是否匹配。
*/
public static void main(String[] args) {
// String s1 = "a*abc";
// String s2 = "abc";
// String s1 = "a*a*a";
// String s2 = "a";
// String s1 = "a.";
// String s2 = "ab";
// String s1 = "a*bd*c";
// String s2 = "abdc";
String s1 = "ada*d*a";
String s2 = "adaa";
System.out.println(isMatch(s1,s2,0,0));
}
public static boolean isMatch(String s1,String s2,int n1,int n2){
int l1 = s1.length();
int l2 = s2.length();
System.out.println("n1:"+n1+"-----n2:"+n2);
if(n1 > l1 || n2 > l2 ){ //有一个字符串超出范围，必然无法相等，返回false
return false;
}else if(n1 == l1 && n2 == l2){ //比较完成，刚好相等，返回true
return true;
}else{ //两个字符串至少一个未到末尾
if(n2 < l2 && n1 < l1 && ((s1.charAt(n1) == s2.charAt(n2)) || s1.charAt(n1) == '.')){ //两个字符串均未到末尾，当对应字符相等或s1的字符为'.'，比较后一位
return isMatch( s1, s2, n1+1, n2+1);
}else if( n1 < l1 && s1.charAt(n1) == '*'){ //s1未到末尾，且对应位置字符为'*'
if(n2>0){ //s2不是处于第一个字符位置，分两种情况：1）当'*'删除前一个字符时，s2也要往前移动一个字符；2)当'*'被忽略时，s2不往前移动
return isMatch( s1, s2, n1+1, n2-1) || isMatch( s1, s2, n1+1, n2);
}else{ //s2处于第一个位置时(由于会出现n2-1的情况，所以有可能在第一个位置)，s1在n1之前的字符都被'*'删除，所以n1+1
return isMatch( s1, s2, n1+1, n2);
}
}else{ //两个位置上的字符不等，此时判断n1之后是否是'*'，如果是，删除这个字符，如果不是，返回false
if(n1+1 < l1 && s1.charAt(n1+1) == '*'){
return isMatch( s1, s2, n1+2, n2);
}else{
return false;
}
}
}
}
}