# What is the time complexity of this problem using backtracking?

• 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;
}
};``````

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