What is the time complexity of this problem using backtracking?


  • 0
    G

    Hi,

    I use backtracking to solve this problem. Following is my code, but I cannot figure out the time complexity of my code. Does any one know this? Thanks!

    class Solution {
    public:
        bool wordPatternMatch(string pattern, string str) {
            if(pattern.length() == 0){
                return str.length() == 0;
            }
            vector<bool> flag(256, true);
            unordered_map<string, char> dict;
            return helper(pattern, str, 0, 0, flag, dict);
        }
        bool helper(string &pattern, string &str, int pinx, int sinx, vector<bool> &flag, unordered_map<string, char> &dict){
            if(pinx == pattern.length()){
                return sinx == str.length();
            }
            for(int i = sinx; i < str.length(); i++){
                string curStr = str.substr(sinx, i - sinx + 1);
                if(dict.find(curStr) == dict.end()){
                    if(flag[pattern[pinx]]){
                        dict.insert(make_pair(curStr, pattern[pinx]));
                        flag[pattern[pinx]] = false;
                        bool curRt = helper(pattern, str, pinx + 1, i + 1, flag, dict);
                        dict.erase(curStr);
                        flag[pattern[pinx]] = true;
                        if(curRt){
                            return true;
                        }
                    }
                }
                else{
                    if(dict[curStr] == pattern[pinx]){
                        bool curRt = helper(pattern, str, pinx + 1, i + 1, flag, dict);
                        if(curRt){
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    };

Log in to reply
 

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