LeetCode/10.cpp at master · nitin-maharana/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * Written by Nitin Kumar Maharana
 * nitin.maharana@gmail.com
 */

class Solution {
    map<pair<int, int>, bool> memory;
    map<pair<int, int>, bool>::iterator it;
    bool result;

public:
    bool isMatchUtil(string &s, string &p, int i, int j)
    {
        if(i == s.length() && j == p.length())
            return true;

        if(i < s.length() && j >= p.length())
            return false;

        it = memory.find(make_pair(i,j));

        if(it != memory.end())
            return it->second;

        if(i < s.length())
        {
            if(j+1 < p.length())
            {
                if(p[j+1] == '*')
                {
                    if(p[j] == '.' || p[j] == s[i])
                    {
                        result = (isMatchUtil(s, p, i, j+2) || isMatchUtil(s, p, i+1, j));
                        memory.insert(make_pair(make_pair(i,j), result));
                        return result;
                    }
                    else
                    {
                        result = isMatchUtil(s, p, i, j+2);
                        memory.insert(make_pair(make_pair(i,j), result));
                        return result;
                    }
                }
            }

            if(p[j] == '.' || p[j] == s[i])
            {
                result = isMatchUtil(s, p, i+1, j+1);
                memory.insert(make_pair(make_pair(i,j), result));
                return result;
            }
            else
                return false;
        }
        else
        {
            if(j+1 < p.length())
                if(p[j+1] == '*')
                {
                    result = isMatchUtil(s, p, i, j+2);
                    memory.insert(make_pair(make_pair(i,j), result));
                    return result;
                }

            return false;
        }
    }

    bool isMatch(string s, string p) {
        return isMatchUtil(s, p, 0, 0);
    }
};