題目描述
請實現一個函數用來匹配包括’.’和’*’的正則表達式。模式中的字符’.’表示任意一個字符，而’*’表示它前面的字符可以出現任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串”aaa”與模式”a.a”和”ab*ac*a”匹配，但是與”aa.a”和”ab*a”均不匹配
算法解析： 同時遍歷兩個字符串，當匹配模式串中的當前值不是’*‘，下一個值為’*‘的時候,而’*’表示它前面的字符可以出現任意次（包含0次）,所以遇到這種情況的時候，這個模式字符可能出現0次，1次，或者多次，所以剩下字符串和模式串的匹配結果由這三種的結果共同影響。
代碼如下：
public boolean match(char[] str, char[] pattern) { if (str == null || pattern == null){ return false; } return matchCore(str, pattern, 0, 0); } PRivate boolean matchCore(char[] str, char[] pattern, int i, int j) { if (i == str.length && j == pattern.length){ //適用于"", "" return true; } if (i == str.length && j != pattern.length){ //適用于"", ".*" while (j != pattern.length){ if(pattern[j] != '*' && (j + 1 >= pattern.length || pattern[j + 1] != '*')){ return false; } j++; } return true; } if (i != str.length && j == pattern.length){ //適用于"abc", "" return false; } if (j == pattern.length - 1){ if (str[i] == pattern[j] || pattern[j] == '.'){ return matchCore(str, pattern, i + 1, j + 1); } return false; } if (pattern[j + 1] == '*'){ if (pattern[j] == str[i] || (pattern[j] == '.' && i != str.length)){ return matchCore(str, pattern, i + 1, j + 2) || matchCore(str, pattern, i + 1, j) || matchCore(str, pattern, i, j + 2); }else{ return matchCore(str, pattern, i, j + 2); } } if (str[i] == pattern[j] || (pattern[j] == '.' && i != str.length)){ return matchCore(str,pattern, i + 1, j + 1); } return false; }新聞熱點
疑難解答
