3ms C++ DFS solution with pruning


  • 0
    S
    class Solution {
    	bool helper(const string &pattern, const string &str, vector<string> &dict, unordered_map<string, char> &s) {
    		if (pattern.empty() && str.empty()) return true;
    		int expectedSize = 0;
    		for (int i = 0; i < pattern.size(); ++i)
    			expectedSize += max((int)dict[pattern[i] - 'a'].size(), 1);
    		if (expectedSize > str.size())
    			return false;
    		for (int i = 0; i < pattern.size(); ++i) {
    			int index = pattern[i] - 'a';
    			if (dict[index].empty()) {
    				for (int j = 0; j <= str.size() - pattern.size(); ++j) {
    					string substr = str.substr(0, j + 1);
    					if (s.find(substr) != s.end())
    						continue;
    					s[substr] = pattern[i];
    					dict[index] = substr;
    					if (helper(pattern.substr(1), str.substr(j + 1), dict, s))
    						return true;
    					s.erase(substr);
    					dict[index] = "";
    				}
    				return false;
    			}
    			else {
    				for (int j = 0; j < dict[index].size(); ++j)
    					if (dict[index][j] != str[j])
    						return false;
    				return (helper(pattern.substr(1), str.substr(dict[index].size()), dict, s));
    			}
    		}
    		return false;
    	}
    public:
    	bool wordPatternMatch(string pattern, string str) {
    		vector<string> dict(26, "");
    		unordered_map<string, char> s;
    		return helper(pattern, str, dict, s);
    	}
    };

Log in to reply
 

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