LC10. Regular Expression Matching

작성일

https://leetcode.com/problems/median-of-two-sorted-arrays/

  • DP 생각 안하고 그냥 일단 재귀로 풀었다.
  • 풀고나니까 너무 느려서 Memo를 추가함.
  • Review: Bottom-up으로도 풀 줄 알아야함.
  • 처음부터 DP를 생각 못하다.. 반성해야함
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
class Solution {
    unordered_map<int, unordered_map<int, bool>> dp;
public:
    bool isMatch(string s, string p) {
        if(!s.size() && !p.size()) return true;
        if(s.size() && !p.size()) return false;
        int ls = s.size(), lp = p.size();
        if(dp.count(ls) && dp[ls].count(lp)) return dp[ls][lp];
        
        if(p.size() <= 1 || p[1] != '*') {
            if(s.empty()) return dp[ls][lp]=false;
            if(p[0] == '.') {
                if(isMatch(s.substr(1), p.substr(1))) return dp[ls][lp]=true;
            } else if(p[0] == s[0]) {
                if(isMatch(s.substr(1), p.substr(1))) return dp[ls][lp]=true;
            }
        } else {
            if(p[0] == '.') {
                for(int i = 0; i <= s.size(); i++)
                    if(isMatch(s.substr(i), p.substr(2))) return dp[ls][lp]=true;
            } else {
                for(int i = 1; i <= s.size() && s[i-1] == p[0]; i++)
                    if(isMatch(s.substr(i), p.substr(2))) return dp[ls][lp]=true;
                if(isMatch(s.substr(0), p.substr(2))) return dp[ls][lp]=true;
            }
        }
        return dp[ls][lp]=false;
    }
};