Easy, Simple Code With 5 Different Approaches🤩| Constant Space
Complexity\n\n\n\n# Pure Recursion\n\nclass Solution {\npublic:\n    bool solve(const string &str, const string &pattern, int strIndex, int patternIndex) {\n   
# Complexity\n![image.png](https://assets.leetcode.com/users/images/f4f48b61-15f5-4d57-8bda-263355dc6fc2_1719736582.2294097.png)\n\n\n# Pure Recursion\n```\nclass Solution {\npublic:\n    bool solve(const string &str, const string &pattern, int strIndex, int patternIndex) {\n        // If both string and pattern are fully traversed, it\'s a match\n        if (strIndex >= str.size() && patternIndex >= pattern.size()) return true;\n\n        // If the string is fully traversed but pattern still has characters left\n        // Only \'*\' can match an empty sequence\n        if (strIndex >= str.size() && patternIndex < pattern.size() && pattern[patternIndex] == \'*\') \n            return solve(str, pattern, strIndex, patternIndex + 1);\n\n        // If one is fully traversed and the other is not, it\'s not a match\n        if (strIndex >= str.size() || patternIndex >= pattern.size()) return false;\n\n        // If current character in pattern is \'*\', it can either match an empty sequence\n        // or one or more characters in the string\n        if (pattern[patternIndex] == \'*\') \n            return solve(str, pattern, strIndex + 1, patternIndex) || solve(str, pattern, strIndex, patternIndex + 1);\n\n        // If current character in pattern is \'?\', it matches any single character in the string\n        if (pattern[patternIndex] == \'?\') \n            return solve(str, pattern, strIndex + 1, patternIndex + 1);\n\n        // If characters match, move to the next character in both string and pattern\n        if (pattern[patternIndex] == str[strIndex]) \n            return solve(str, pattern, strIndex + 1, patternIndex + 1);\n\n        // If none of the above conditions are met, it\'s not a match\n        return false;\n    }\n\n    bool isMatch(string str, string pattern) {\n        return solve(str, pattern, 0, 0);\n    }\n};\n```\n\n# Memoization\n```\nclass Solution {\npublic:\n    bool solve(const string &str, const string &pattern, int strIndex, int patternIndex, vector<vector<int>> &memo) {\n        // Return the cached result if it exists\n        if (memo[strIndex][patternIndex] != -1) return memo[strIndex][patternIndex];\n\n        // If both string and pattern are fully traversed, it\'s a match\n        if (strIndex >= str.size() && patternIndex >= pattern.size()) \n            return memo[strIndex][patternIndex] = true;\n\n        // If the string is fully traversed but pattern still has characters left\n        // Only \'*\' can match an empty sequence\n        if (strIndex >= str.size() && patternIndex < pattern.size() && pattern[patternIndex] == \'*\') \n            return memo[strIndex][patternIndex] = solve(str, pattern, strIndex, patternIndex + 1, memo);\n\n        // If one is fully traversed and the other is not, it\'s not a match\n        if (strIndex >= str.size() || patternIndex >= pattern.size()) \n            return memo[strIndex][patternIndex] = false;\n\n        // If current character in pattern is \'*\', it can either match an empty sequence\n        // or one or more characters in the string\n        if (pattern[patternIndex] == \'*\') \n            return memo[strIndex][patternIndex] = solve(str, pattern, strIndex, patternIndex + 1, memo) || solve(str, pattern, strIndex + 1, patternIndex, memo);\n\n        // If current character in pattern is \'?\', it matches any single character in the string\n        if (pattern[patternIndex] == \'?\') \n            return memo[strIndex][patternIndex] = solve(str, pattern, strIndex + 1, patternIndex + 1, memo);\n\n        // If characters match, move to the next character in both string and pattern\n        if (pattern[patternIndex] == str[strIndex]) \n            return memo[strIndex][patternIndex] = solve(str, pattern, strIndex + 1, patternIndex + 1, memo);\n\n        // If none of the above conditions are met, it\'s not a match\n        return memo[strIndex][patternIndex] = false;\n    }\n\n    bool isMatch(string str, string pattern) {\n        // Initialize the memoization table with -1 indicating uncalculated states\n        vector<vector<int>> memo(str.size() + 1, vector<int>(pattern.size() + 1, -1));\n        return solve(str, pattern, 0, 0, memo);\n    }\n};\n```\n\n# Tabulation\n```\nclass Solution {\npublic:\n    bool isMatch(string str, string pattern) {\n        // Create a 2D DP table with extra space for boundary conditions\n        vector<vector<int>> dp(str.size() + 1, vector<int>(pattern.size() + 1, 0));\n\n        // Initialize the DP table from the end towards the start\n        for (int strIndex = str.size() ; strIndex >= 0; strIndex--) {\n            for (int patternIndex = dp[strIndex].size() - 1; patternIndex >= 0; patternIndex--) {\n                if (strIndex >= str.size() && patternIndex >= pattern.size()) {\n                    // If both string and pattern are fully traversed, it\'s a match\n                    dp[strIndex][patternIndex] = true;\n                } else if (strIndex >= str.size() && patternIndex < pattern.size() && pattern[patternIndex] == \'*\') {\n                    // If string is fully traversed and the current pattern character is \'*\', it can match an empty sequence\n                    dp[strIndex][patternIndex] = dp[strIndex][patternIndex + 1];\n                } else if (strIndex >= str.size() || patternIndex >= pattern.size()) {\n                    // If one is fully traversed and the other is not, it\'s not a match\n                    dp[strIndex][patternIndex] = false;\n                }\n            }\n        }\n\n        // Fill the DP table from the end towards the start\n        for (int strIndex = str.size() - 1; strIndex >= 0; strIndex--) {\n            for (int patternIndex = pattern.size() - 1; patternIndex >= 0; patternIndex--) {\n                if (pattern[patternIndex] == \'*\') {\n                    // If current pattern character is \'*\', it can match zero or more characters\n                    dp[strIndex][patternIndex] = dp[strIndex][patternIndex + 1] || dp[strIndex + 1][patternIndex];\n                } else if (pattern[patternIndex] == \'?\') {\n                    // If current pattern character is \'?\', it matches any single character\n                    dp[strIndex][patternIndex] = dp[strIndex + 1][patternIndex + 1];\n                } else if (pattern[patternIndex] == str[strIndex]) {\n                    // If current characters match, move to the next characters in both string and pattern\n                    dp[strIndex][patternIndex] = dp[strIndex + 1][patternIndex + 1];\n                } else {\n                    // If none of the above conditions are met, it\'s not a match\n                    dp[strIndex][patternIndex] = false;\n                }\n            }\n        }\n\n        // Return the result of matching the entire string with the entire pattern\n        return dp[0][0];\n    }\n};\n```\n\n# Tabulation With Space Optimization\n```\nclass Solution {\npublic:\n    bool isMatch(string str, string pattern) {\n        int strLength = str.size();\n        int patternLength = pattern.size();\n        \n        // Initialize current and next DP arrays\n        vector<int> curr(patternLength + 1, 0);\n        vector<int> nxt(patternLength + 1, 0);\n        \n        // Base case: an empty pattern matches an empty string\n        nxt[patternLength] = 1;\n\n        // Fill the DP array for the base cases when the string is empty\n        for (int patternIndex = patternLength; patternIndex >= 0; patternIndex--) {\n            if(patternIndex>=patternLength)\n                nxt[patternIndex] = 1;\n            else if (pattern[patternIndex] == \'*\') \n                nxt[patternIndex] = nxt[patternIndex + 1]; \n            else \n                nxt[patternIndex] = 0; \n        }\n\n        // Fill the DP table from the end towards the start\n        for (int strIndex = strLength - 1; strIndex >= 0; strIndex--) {\n            for (int patternIndex = patternLength - 1; patternIndex >= 0; patternIndex--) {\n                if (pattern[patternIndex] == \'*\') {\n                    // If current pattern character is \'*\', it can match zero or more characters\n                    curr[patternIndex] = curr[patternIndex + 1] || nxt[patternIndex]; \n                } else if (pattern[patternIndex] == \'?\') {\n                    // If current pattern character is \'?\', it matches any single character\n                    curr[patternIndex] = nxt[patternIndex + 1];\n                } else if (pattern[patternIndex] == str[strIndex]) {\n                    // If current characters match, move to the next characters in both string and pattern\n                    curr[patternIndex] = nxt[patternIndex + 1];\n                } else {\n                    // If none of the above conditions are met, it\'s not a match\n                    curr[patternIndex] = 0; \n                }\n            }\n            // Move current results to next for the next iteration\n            nxt = curr; \n        }\n\n        // Return the result of matching the entire string with the entire pattern\n        return nxt[0];\n    }\n};\n```\n\n# Tabulation With More Space Optimization\n```\nclass Solution {\npublic:\n    bool isMatch(string str, string pattern) {\n        int strLength = str.size();\n        int patternLength = pattern.size();\n        \n        // Initialize current and next DP arrays\n        vector<int> curr(2000 + 1, 0);\n        vector<int> nxt(2000 + 1, 0);\n        \n        // Base case: an empty pattern matches an empty string\n        nxt[patternLength] = 1;\n\n        // Fill the DP array for the base cases when the string is empty\n        for (int patternIndex = patternLength; patternIndex >= 0; patternIndex--) {\n            if(patternIndex>=patternLength)\n                nxt[patternIndex] = 1;\n            else if (pattern[patternIndex] == \'*\') \n                nxt[patternIndex] = nxt[patternIndex + 1]; \n            else \n                nxt[patternIndex] = 0; \n        }\n\n        // Fill the DP table from the end towards the start\n        for (int strIndex = strLength - 1; strIndex >= 0; strIndex--) {\n            for (int patternIndex = patternLength - 1; patternIndex >= 0; patternIndex--) {\n                if (pattern[patternIndex] == \'*\') {\n                    // If current pattern character is \'*\', it can match zero or more characters\n                    curr[patternIndex] = curr[patternIndex + 1] || nxt[patternIndex]; \n                } else if (pattern[patternIndex] == \'?\') {\n                    // If current pattern character is \'?\', it matches any single character\n                    curr[patternIndex] = nxt[patternIndex + 1];\n                } else if (pattern[patternIndex] == str[strIndex]) {\n                    // If current characters match, move to the next characters in both string and pattern\n                    curr[patternIndex] = nxt[patternIndex + 1];\n                } else {\n                    // If none of the above conditions are met, it\'s not a match\n                    curr[patternIndex] = 0; \n                }\n            }\n            // Move current results to next for the next iteration\n            nxt = curr; \n        }\n\n        // Return the result of matching the entire string with the entire pattern\n        return nxt[0];\n    }\n};\n```
['C++']