題目描述
請實作一個函式用來匹配包括'.'和''的正則運算式，模式中的字符'.'表示任意一個字符，而''表示它前面的字符可以出現任意次（包含0次）， 在本題中，匹配是指字串的所有字符匹配整個模式，例如，字串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配
思路
結發編程，，，
時間復雜度O(n)，空間復雜度O(n)，
代碼
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;
}
//str未到尾，pattern到尾，匹配失敗
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//str到尾，pattern未到尾(不一定匹配失敗，因為a*可以匹配0個字符)
if (strIndex == str.length && patternIndex != pattern.length) {
//只有pattern剩下的部分類似a*b*c*的形式，才匹配成功
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
return false;
}
//str未到尾，pattern未到尾
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2)//*匹配0個，跳過
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)//*匹配1個，跳過
|| matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1個，再匹配str中的下一個
} else {
//直接跳過*（*匹配到0個）
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
筆記
，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205859.html
標籤：其他
上一篇：構建乘積陣列
下一篇：表示數值的字串