Untitled

mail@pastecode.io avatar
unknown
plain_text
15 days ago
2.5 kB
4
Indexable
Never
class Solution {
public:
    int find(const string_view& s, const string_view& p) {
        int i{}, j{};
        for(; i < s.size(); ++i) {
            for(; j < p.size(); ++j) {
                if(p[j] != s[i + j] && p[j] != '.')
                    break;
            }
            if(j == p.size())
                return i;
            j = 0;
        }
        return -1;
    }

    bool isMatch(string s, string p) {
        struct Item {
            int shift{-1};
            string word;
            string reps;
        };

        Item item;
        vector<Item> items;

        int minSize = p.size();
        for(int j{}; j < p.size(); ++j) {
            if(j+1 < p.size() && p[j+1] == '*') {
                minSize -= 2;
                if(!item.word.empty())
                {
                    items.push_back(item);
                    item = {};
                }
                item.reps += p[j];
                ++j;
            }
            else {
                item.word += p[j];
            }
        }
        if(!item.word.empty() || !item.reps.empty())
            items.push_back(item);

        if(s.size() < minSize)
            return false;

        stack<int> shifts{};
        shifts.push(0);
        for(int i{} ; i < items.size(); ++i)
        {
            int f = s.size();

            if(!items[i].word.empty()) {
                int shift = items[i].shift >= 0 ? items[i].shift : shifts.top();
                f = find(string_view(s.c_str() + shift), items[i].word);
                if(f < 0)
                    return false;
                f += shift;
                items[i].shift = f + 1; // next possible shift

                if(i == items.size()-1 && f + items[i].word.size() != s.size()) {
                    i -=1;
                    continue;
                }
            }

            int c{shifts.top()};
            for(int r : items[i].reps) {
                for(; c < f; ++c) {
                    if(r != s[c] && r != '.')
                        break;
                }
            }

            if(c == f) {
                shifts.push(min(s.size(), f + items[i].word.size()));
            } else {
                if(i > 0)
                    items[i].shift = -1;
                i -= 2;
                if(i < -1)
                    return false;
                shifts.pop();
            }
        }

        return true;
    }
};
Leave a Comment