# Wildcard Matching - HJ

Aug 17th, 2020
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.
4. bool helper_isMatch(string text, string pattern, int textIndex, int patternIndex,
5. unordered_map<string, bool> &memo){
6.
7. string key = to_string(textIndex) + "|" + to_string(patternIndex);
8. if(memo.find(key)!=memo.end()){
9. return memo[key];
10. }
11.
12. if(textIndex==text.size() && patternIndex==pattern.size()){
13. return true;
14. }
15. if(textIndex<text.size() && patternIndex==pattern.size()){
16. return false;
17. }
18. if(textIndex==text.size() && patternIndex<pattern.size()){
19. if(pattern[patternIndex]=='*'){
20. memo[key] = helper_isMatch(text, pattern, textIndex, patternIndex+1, memo);
21. return memo[key];
22. }else{
23. return false;
24. }
25. }
26.
27.
28.
29. bool to_return = false;
30. if(pattern[patternIndex]=='*'){
31. to_return = helper_isMatch(text, pattern, textIndex+1, patternIndex, memo) ||
32. helper_isMatch(text, pattern, textIndex, patternIndex+1, memo);
33. }else{
34. if(pattern[patternIndex]=='?'){
35. to_return = helper_isMatch(text, pattern, textIndex+1, patternIndex+1, memo);
36. }else if(pattern[patternIndex]==text[textIndex]){
37. to_return = helper_isMatch(text, pattern, textIndex+1, patternIndex+1, memo);
38. }else{
39. to_return = false;
40. }
41. }
42.
43. memo[key] = to_return;