請實作一個函式用來匹配包括 '.' 和 '*' 的正則運算式，模式中的字符' .' 表示任意一個字符，而 '*' 表示它前面的字符可以出現任意次（包含 0 次）， 在本題中，匹配是指字串的所有字符匹配整個模式，例如，字串 "aaa" 與模式 "a.a" 和 "ab*ac*a" 匹配，但是與 "aa.a" 和 "ab*a" 均不匹配
解題思路
將模式與字串逐個匹配，當模式中的第二個字符不是 * 時：
- 如果字串第一個字符和模式中的第一個字符相匹配，那么字串和模式都后移一個字符，然后匹配剩余的
- 如果字串第一個字符和模式中的第一個字符相不匹配，直接回傳 false
而當模式中的第二個字符是 * 時：如果字串第一個字符跟模式第一個字符不匹配，則模式后移兩個字符，繼續匹配，如果字串第一個字符跟模式第一個字符匹配，可以有三種匹配方式：
- 模式后移兩個字符，相當于 x* 被忽略
- 字串后移一個字符，模式后移兩個字符
- 字串后移一字符，模式不變，即繼續匹配字符下一位，因為 * 可以匹配多位
public class Solution {
public boolean match(char[] str, char[] pattern) {
if(str == null || pattern == null) {
return false;
}
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
// 有效性檢驗：str 到尾，pattern 到尾，匹配成功
if(strIndex == str.length && patternIndex == pattern.length) {
return true;
}
// pattern 先到尾，匹配失敗
if(strIndex != str.length && patternIndex == pattern.length) {
return false;
}
// 模式第2個是*，且字串第1個跟模式第1個匹配,分3種匹配模式；如不匹配，模式后移2位
if(patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
return matchCore(str, strIndex, pattern, patternIndex + 2) ||
matchCore(str, strIndex + 1, pattern, patternIndex + 2) ||
matchCore(str, strIndex + 1, pattern, patternIndex);
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
// 模式第2個不是*，且字串第1個跟模式第1個匹配，則都后移1位，否則直接回傳false
if((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235329.html
標籤：其他
下一篇：表示數值的字串