[LeetCode] Wildcard Matching
Wildcard Matching Implement wildcard pattern matching with support for
問題解決の考え方:
この問題はhttp://blog.csdn.net/kangrydotnet/article/details/46624353同様に、ここの*番号はRegular Expression Matchingとは異なります.Regular Expression Matchingを使用してアーキテクチャを開発し、再帰的な方法を使用することができます.ただし、タイムアウトの問題が発生します.
"abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
解析により、再帰呼び出し時に計算が繰り返されます.s[0...i]がp[0...j]と一致するかどうかを2次元配列d[i][j]で記録することができる.
最終的な方法は水中の魚を参考にします.http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html、具体的にはまだよく分かりません.
'?'
and '*'
. '?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
問題解決の考え方:
この問題はhttp://blog.csdn.net/kangrydotnet/article/details/46624353同様に、ここの*番号はRegular Expression Matchingとは異なります.Regular Expression Matchingを使用してアーキテクチャを開発し、再帰的な方法を使用することができます.ただし、タイムアウトの問題が発生します.
class Solution {
public:
bool isMatch(string s, string p) {
return matchHelper(s, p, 0, 0);
}
bool matchHelper(string& s, string& p, int i, int j){
if(p[j]=='\0'){
return s[i]=='\0';
}
if(p[j]!='*'){
return ((s[i]==p[j] || p[j]=='?'&&s[i]!='\0') && matchHelper(s, p, i+1, j+1));
}
//p[j]=='*'
while(s[i]!='\0'){
if(matchHelper(s, p, i, j+1)) return true;
i++;
}
return matchHelper(s, p, i, j+1);
}
};
「aaabbbaabaaaaaaabaaabaaabaaabaaabaaababababbabbbbaababababbabbaaaba」、「a*******b」と入力すると、上記のコードはタイムアウトします.なぜなら連続的な*があるからです.そこで入力を修正し、a*****bをa*bに変更し、以下のようにする.class Solution {
public:
bool isMatch(string s, string p) {
string newP = "";
for (int i = 0; i < p.length(); i++){
if (i>0 && p[i - 1] == p[i] && p[i]=='*'){
continue;
}
newP += p[i];
}
return matchHelper(s, newP, 0, 0);
}
bool matchHelper(string& s, string& p, int i, int j){
if (p[j] == '\0'){
return s[i] == '\0';
}
if (p[j] != '*'){
return ((s[i] == p[j] || p[j] == '?'&&s[i] != '\0') && matchHelper(s, p, i + 1, j + 1));
}
//p[j]=='*'
while (s[i] != '\0'){
if (matchHelper(s, p, i, j + 1)) return true;
i++;
}
return matchHelper(s, p, i, j + 1);
}
};
入力が非常に大きい場合、まだタイムアウトしています."abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
解析により、再帰呼び出し時に計算が繰り返されます.s[0...i]がp[0...j]と一致するかどうかを2次元配列d[i][j]で記録することができる.
class Solution {
public:
bool isMatch(string s, string p) {
string newP = "";
for (int i = 0; i < p.length(); i++){
if (i>0 && p[i - 1] == p[i] && p[i] == '*'){
continue;
}
newP += p[i];
}
int sLen = s.length();
int pLen = newP.length();
vector<vector<bool>> d(sLen + 1, vector<bool>(pLen + 1, true));
return matchHelper(s, newP, 0, 0, d);
}
bool matchHelper(string& s, string& p, int i, int j, vector<vector<bool>>& d){
if (p[j] == '\0'){
return (d[i][j] = s[i] == '\0');
}
if (p[j] != '*'){
return (d[i][j] = (s[i] == p[j] || p[j] == '?'&&s[i] != '\0') && d[i + 1][j + 1] && matchHelper(s, p, i + 1, j + 1, d));
}
//p[j]=='*'
while (s[i] != '\0'){
if ((d[i][j] = d[i][j + 1] && matchHelper(s, p, i, j + 1, d))) return true;
i++;
}
return (d[i][j] = d[i][j + 1] && matchHelper(s, p, i, j + 1, d));
}
};
ここでは短絡原則を用いる.速度は非常に速いが、メモリオーバーフローエラーが発生する.空間複雑度がO(m*n)であるためである.最終的な方法は水中の魚を参考にします.http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html、具体的にはまだよく分かりません.
class Solution {
public:
bool isMatch(string s, string p) {
bool star = false;
int sStart = 0, pStart = 0;
int str, ptr;
for(str=sStart, ptr = pStart; s[str]!='\0'; str++, ptr++){
switch(p[ptr]){
case '?':
break;
case '*':
star = true;
sStart = str, pStart = ptr;
while(p[pStart]=='*'){
pStart++;
}
if(p[pStart]=='\0'){
return true;
}
str = sStart - 1;
ptr = pStart - 1;
break;
default:
if(s[str]!=p[ptr]){
if(!star){
return false;
}
sStart++;
str = sStart-1;
ptr = pStart-1;
}
break;
}
}
while(p[ptr]=='*')
ptr++;
return p[ptr]=='\0';
}
};