【LeetCode】44.Wildcard Matching解法及び注釈
44. Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'. 1. '?' Matches any single character. 2. '*' Matches any sequence of characters (including the empty sequence). 3. The matching should cover the entire input string (not partial). 4. The function prototype should be: bool isMatch(const char *s, const char *p) 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
【分析】
この問題は、2つの文字列を指定して一致するかどうかを判断する「ワイルドカード」マッチング問題です.文字列sはワイルドカードを含まない普通の文字列であり、文字列pはワイルドカード「*」と「?の文字列は、文字列pがsと一致するかどうかを判断する必要があります.そのため、2つの文字列の文字を逐次比較する必要があります.
テーマから与えられたexamplesに基づいて,いくつかの基本規則を導くことができる:(ps,ppを文字列sとpの下付きとする)
1.s[ps]==p[pp]の場合、下付き(pp++;ps++)を直接移動し、次の位置の文字が等しいかどうかを比較する.
2.p[pp]='?',では、対応するs[ps]がどんな文字であってもいわゆる、1の処理と同じである.
3.p[pp]=「*」の場合、本題の難点が来た.「*」は任意の文字と文字列に一致することができるが、それがsの中のどの文字と一致するのか、私たちは後の文字を比較する必要がある.例えば、s=「abcacc」、p=「abc*c」、前の3つの文字はすべて一致している.下の文字を移動すればよい.ps=pp=3、すなわち[ps]=「a」、p[pp]=「*」の場合、私たちは「*」がどの文字に一致するか分からないが、後の比較結果に基づいて決定するしかない.私たちはppを次のビットに移動する:p[4]=「c」、s[3]と一致しない.そのため、「*」はs[3]を一致させる必要がある.s[3]がp[3]で一致していると判断しても、p[3]=「*」がs[3]と一致しているとは確定できない.それは複数の文字に一致するので、「*」の位置を保存する必要がある.私達は引き続きpsを移動して、s[ps]=s[4]='c'で、この時ppは3に戻って、同じく、私達はppを移動して、p[pp]=p[4]='c'で、両者はちょうど一致して、同時にppを移動して、ps、sを発見します[5]!=p[5],この場合,我々は「遡及法」の考え方を用いて,ppを再び「*」の位置3に移動し,psを前回すでに「*」で一致したps=3の位置の次の位置に遡り,pp=3の「*」でps=4の位置の文字を引き続き一致させ,psを移動する必要がある.s[ps]=s[5]とp[pp]=p[3]を比較し、p[3]='*'、ppを移動し、次のビットを比較すると、p[4]=s[5]が発見され、同時にpp、psを移動し、文字列sの末尾に達し、サイクル比較が終了する.
4.ループ比較が終了した後、s=「abcacc」、p=「abc*cd」などのpとsのマッチングを決定することはできません.pは同時に文字列の末尾に到達するか、pの後ろに残っている文字がすべて'*'*':s=「abcacc」、p=「abc********」であってこそ、マッチングを形成することができます.
【アルゴリズムおよびコメント】
Implement wildcard pattern matching with support for '?' and '*'. 1. '?' Matches any single character. 2. '*' Matches any sequence of characters (including the empty sequence). 3. The matching should cover the entire input string (not partial). 4. The function prototype should be: bool isMatch(const char *s, const char *p)
【分析】
この問題は、2つの文字列を指定して一致するかどうかを判断する「ワイルドカード」マッチング問題です.文字列sはワイルドカードを含まない普通の文字列であり、文字列pはワイルドカード「*」と「?の文字列は、文字列pがsと一致するかどうかを判断する必要があります.そのため、2つの文字列の文字を逐次比較する必要があります.
テーマから与えられたexamplesに基づいて,いくつかの基本規則を導くことができる:(ps,ppを文字列sとpの下付きとする)
1.s[ps]==p[pp]の場合、下付き(pp++;ps++)を直接移動し、次の位置の文字が等しいかどうかを比較する.
2.p[pp]='?',では、対応するs[ps]がどんな文字であってもいわゆる、1の処理と同じである.
3.p[pp]=「*」の場合、本題の難点が来た.「*」は任意の文字と文字列に一致することができるが、それがsの中のどの文字と一致するのか、私たちは後の文字を比較する必要がある.例えば、s=「abcacc」、p=「abc*c」、前の3つの文字はすべて一致している.下の文字を移動すればよい.ps=pp=3、すなわち[ps]=「a」、p[pp]=「*」の場合、私たちは「*」がどの文字に一致するか分からないが、後の比較結果に基づいて決定するしかない.私たちはppを次のビットに移動する:p[4]=「c」、s[3]と一致しない.そのため、「*」はs[3]を一致させる必要がある.s[3]がp[3]で一致していると判断しても、p[3]=「*」がs[3]と一致しているとは確定できない.それは複数の文字に一致するので、「*」の位置を保存する必要がある.私達は引き続きpsを移動して、s[ps]=s[4]='c'で、この時ppは3に戻って、同じく、私達はppを移動して、p[pp]=p[4]='c'で、両者はちょうど一致して、同時にppを移動して、ps、sを発見します[5]!=p[5],この場合,我々は「遡及法」の考え方を用いて,ppを再び「*」の位置3に移動し,psを前回すでに「*」で一致したps=3の位置の次の位置に遡り,pp=3の「*」でps=4の位置の文字を引き続き一致させ,psを移動する必要がある.s[ps]=s[5]とp[pp]=p[3]を比較し、p[3]='*'、ppを移動し、次のビットを比較すると、p[4]=s[5]が発見され、同時にpp、psを移動し、文字列sの末尾に達し、サイクル比較が終了する.
4.ループ比較が終了した後、s=「abcacc」、p=「abc*cd」などのpとsのマッチングを決定することはできません.pは同時に文字列の末尾に到達するか、pの後ろに残っている文字がすべて'*'*':s=「abcacc」、p=「abc********」であってこそ、マッチングを形成することができます.
【アルゴリズムおよびコメント】
class Solution {
public:
bool isMatch(string s,string p)
{
int LS,LP;// ，
LS=s.length();
LP=p.length();
if(LS==0&&LP==0)return true;// ， true
else if(LS==0&&LP!=0)//s ，p '*' ， true， false
{
int i=0;
while(p[i]=='*')i++;
if(i==LP)return true;// p '*'
else return false;
}
else
{
int pp,ps;//
pp=ps=0;//
int matchIndex=0;//
int starIndex=0;// '*'
bool flag=false;// '*'
while(ps<LS)// ， p s， s ，p s
{
if(s[ps]==p[pp]||p[pp]=='?')// ， ，
{
pp++;
ps++;
}
else if(p[pp]=='*')// '*'
{
flag=true;// '*'
starIndex=pp;// ‘*’
matchIndex=ps;// S
pp++;// pp， s ， '*'
}
else
{
if(!flag)return false;// ， '*'， ，
pp=starIndex;// '*'， pp“ ” '*'
ps=matchIndex;//ps“ ” ，
ps++;// s ， ps ，
}
}
while(p[pp]=='*'&&pp<LP)pp++;// s ， p ， '*'
if(p[pp]=='\0')return true;
else return false;
}
}
};