LC44. Wildcard Matching

작성일

문제: https://leetcode.com/problems/trapping-rain-water/

  • 유사한 문제를 풀었어서 익숙한 문제. 한번에 코드를 썼는데 정답이여서 고무적이었다.
  • $O(N^2)$ 시간 공간을 사용하는 전형적인 문자열 DP문제 방식으로 풀었다.
  • 그치면 다른 사람의 풀이를 보니.. 선형시간에 상수공간을 사용하는 접근법이 있다. Greedy 한 접근이 필요할듯.. 복습하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<int>> dp;
        dp.resize(p.size()+1, vector<int>(s.size()+1));
        
        dp[0][0] = 1;
        for(int i = 1; i <= p.size(); i++)
            if(dp[i-1][0] && p[i-1] == '*')
                dp[i][0] = 1;
        
        for(int i = 1; i <= p.size(); i++) {
            for(int j = 1; j <= s.size(); j++) {
                if(p[i-1] == s[j-1] && dp[i-1][j-1])
                    dp[i][j] = 1;
                if(p[i-1] == '?' && dp[i-1][j-1])
                    dp[i][j] = 1;
                if(p[i-1] == '*' && (dp[i-1][j] || dp[i-1][j-1] || dp[i][j-1]))
                    dp[i][j] = 1;
            }
        }
        return dp[p.size()][s.size()];
    }
};