ワイルドカードにマッチするか確かめる – 面接準備

If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.

addFilter(filter)
isInBlackList(string)

filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars.

Amazon Interview Question for Software Engineers

ワイルドカードを含む探索を再帰を使って実装してみます。

文字列: abc
パターン: a*c

がマッチするかは最初の文字を比較します

文字列: [a]bc
パターン: [a]*c

不一致ならfalse、一致するなら最初の1文字を取り除いて

文字列: bc
パターン: *c

がマッチするか確かめればよいということです。

ポインタを2つ用意します。マッチするか確かめる文字列のポインタと、パターンのポインタです。

1文字ずつ読み進めていきますが、もし一致しないものが見つかればそこでfalseを返します。

パターンを最後まで読み終えてしまった場合、検証する文字列も終わりならtrue, 違うならfalseを返します。

最後に*に当たった場合は

• 0文字マッチする場合→単に*を飛ばして残りがマッチするか再帰
• 1文字以上マッチする場合→テキストを1文字飛ばして再帰、+1する都合上テキストの終端を確認

bool match( const char *text, const char *pattern )
{
    while(true)
    {
        if( *pattern == '\0' )
        {
            if( *text == '\0' )
                return true;
            else
                return false;
        }

        if( *pattern == '*' )
        {
            bool a = match( text, pattern + 1 );
            bool b = *text != '\0' && match( text + 1, pattern );

            return a || b;
        }

        if( *text == *pattern )
        {
            text++;
            pattern++;
        }
        else
        {
            return false;
        }
    }

    return false;
}

任意の文字にマッチする?も探すのなら、テキストとパターンを1個進めて再帰も入れればOK。

コード全体は

vector<string> filter;

bool match( const char *text, const char *pattern )
{
    while(true)
    {
        if( *pattern == '\0' )
        {
            if( *text == '\0' )
                return true;
            else
                return false;
        }

        if( *pattern == '*' )
        {
            bool a = match( text, pattern + 1 );
            bool b = *text != '\0' && match( text + 1, pattern );

            return a || b;
        }

        if( *text == *pattern )
        {
            text++;
            pattern++;
        }
        else
        {
            return false;
        }
    }

    return false;
}


void addFilter(const string &f)
{
    filter.push_back(f);
}

bool isInBlackList(const string &text)
{
    bool result = false;
    for( auto f: filter )
    {
        if( match( text.c_str(), f.c_str() ) == true )
            result = true;
    }

    return result;
}


int main()
{
    addFilter("a*b");
    addFilter("aa*b");
    addFilter("abc");
    addFilter("abdr*");

    // true
    assert( isInBlackList("accb") == true );
    assert( isInBlackList("ab") == true );
    assert( isInBlackList("aaxvfbb") == true );
    assert( isInBlackList("abc") == true );
    assert( isInBlackList("abdreee") == true );

    // false
    assert( isInBlackList("ax") == false );
    assert( isInBlackList("aa") == false );
    assert( isInBlackList("bb") == false );
}