Fork me on GitHub

Wildcard Matching

Posted on

Description

https://leetcode.com/problems/wildcard-matching/description/

Naive Code (TLE)

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
class Solution {
public:
    bool isMatch(string s, string p) {
        return findMatch(s, p, 0, 0);
    }
    
    bool findMatch(string s, string p, int s_index, int p_index) {
        if (s.length() == s_index && p_index == p.length()) return true;
        if (p_index == p.length()) return false;
        if (s_index == s.length()){
            if (p[p_index] == '*') {
                return findMatch(s, p, s_index, p_index + 1);
            }else {
                return false;
            }
        }
        
        char p_char = p[p_index], s_char = s[s_index];
        if (p_char == '?' || p_char == s_char) {
            return findMatch(s, p, s_index + 1, p_index + 1);
        }
        if (p_char == '*'){
            for(int i = s_index; i <= s.length(); i++) {
                if(findMatch(s, p, i, p_index + 1) ){
                    return true;
                }
            }
            return false;
        }
        
        return false;
    }
};