How to improve my solution? It's Time limit exceeded


  • 0

    How to improve the solution to avoid the TLE?

    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            // Input validation.
            if (s == NULL || p == NULL) return false;
            
            int s_start = 0;
            int p_start = 0;
            string s_string(s);
            string p_string(p);
            
            return helper(s_string, s_start, p_string, p_start);
        }
        
        bool helper(const string &s_string, int s_index,
                    const string &p_string, int p_index) {
        
            // Base case.
            if (p_index >= p_string.length()) return s_index >= s_string.length();
            if (p_index == p_string.length() - 1) {
                return (s_index == s_string.length() - 1) &&
                       (p_string[p_index] == s_string[s_index] ||
                        p_string[p_index] == '.');
            }
            
            int sLen = s_string.length();
            int pLen = p_string.length();
            
            if (p_index + 1 < pLen && p_string[p_index + 1] != '*') {
                if (p_string[p_index] == s_string[s_index] ||
                    p_string[p_index] == '.') {
                    // Do recursion.    
                    return helper(s_string, s_index + 1, p_string, p_index + 1);
                } else return false;
                
            } else {
                while (s_index < sLen) {
                    // Do recursion.
                    if (helper(s_string, s_index, p_string, p_index + 2)) return true;
                    s_index ++;
                }
                return false;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.