Advertisement
HjHimansh

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;
  44. return to_return;
  45. }
  46.  
  47. bool isMatch(string s, string p) {
  48. unordered_map<string, bool> memo;
  49. return helper_isMatch(s, p, 0, 0, memo);
  50. }
  51. };
Advertisement
RAW Paste Data Copied
Advertisement