Developer's notes

Дикость продолжается

Кратко объясню идеи сниппета из прошлого поста:
Идём по строке и образцу, если оба символа совпадает, просто наращиваем оба индекса, если в образце стоит знак вопроса - делаем тоже самое, т.к. он совпадает с любым другим символом, при первом же не совпадении – рапортуем о неудаче. Всё предельно просто.

Ну теперь попробуем вернуть "звёздочки": по определению '*' соответствует нулю либо любому иному количеству символов...то есть – она не соответствует ничему – весь вопрос в том, чему соответствует символы за ней...Что если мы попробуем матчить остаток строки остатку шаблона, а если не сможем – просто нарастим индекс в строке? Вот примерно такой набросочек:

class Solution {
public:
    bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        if (p.empty())
        {
            return s.empty();
        }

        return isMatchImpl(s, p, sIndex, pIndex);
    }

    bool isMatchImpl(const string& s, string& p, int sIndex, int pIndex)
    {
        while (sIndex < s.size() && pIndex < p.size())
        {
            if (p[pIndex] == '?')
            {
                ++sIndex, ++pIndex;
                continue;
            }

            if (p[pIndex] == '*')
            {
                while (pIndex < p.size() - 1 && p[pIndex + 1] == '*')
                {
                    ++pIndex;
                }

                return matchStar(s, p, sIndex, ++pIndex);
            }

            if (p[pIndex] == s[sIndex])
            {
                ++sIndex, ++pIndex;
                continue;
            }

            return false;
        }

        if (sIndex < s.size() && (pIndex = p.size()))
        {
            return false;
        }

        if (sIndex == s.size())
        {
            while(pIndex < p.size())
            {
                if (p[pIndex] != '*')
                {
                    return false;
                }

                ++pIndex;
            }

            return true;
        }

        return true;
    }

    bool matchStar(const string& s, string& p, int sIndex, int pIndexAtStop)
    {
        // there is nothing after the star
        if (pIndexAtStop >= p.size())
        {
            return true;
        }

        auto stopCh = p[pIndexAtStop];

        cout << "stopchar = " << stopCh << endl;

        while (sIndex < s.size())
        {
            if (s[sIndex] == stopCh || stopCh == '?')
            {
                auto matched = isMatchImpl(s, p, sIndex + 1, pIndexAtStop + 1);

                if (matched)
                {
                    return true;
                }
            }

            ++sIndex;
        }

        return false;

    }
}

Это почти работает, в следующий раз – объясню в чём загвоздка и завершу этот маленький цикл.

#today #c_plus_plus #leetcode #algo #ToBeContinued

👍1

70 views05:02