My C++ 26ms backtracking solution with trie and hashtable


  • 0
    typedef struct TrieNode
    {
    	bool isStr = false;
    	TrieNode *next[26] = { nullptr };
    	unordered_set<string> dict;
    } Trie;
    class Solution 
    {
    private:
    	Trie *root;
    	vector<vector<string>> res;
    	vector<string> solution;
    	int N;
    	void insert(const string &word)
    	{
    		if (root == nullptr) return;
    		TrieNode *curr = root;
    		for (int i = 0; i < N; ++i)
    		{
    			curr->dict.insert(word);
    			int pos = word[i] - 'a';
    			if (curr->next[pos] == nullptr)
    				curr->next[pos] = new TrieNode();
    			curr = curr->next[pos];
    		}
    		curr->isStr = true;
    	}
    	void backtracking(int pos)
    	{
    		if (pos == N)
    		{
    			res.push_back(solution);
    			return;
    		}
    		TrieNode *curr = root;
    
    		for (int i = 0; i < pos; ++i)
    			if (!(curr = curr->next[solution[i][pos] - 'a']))
    				return;
    		for (auto &word : curr->dict)
    		{
    			solution[pos] = word;
    			backtracking(pos + 1);
    		}
    	}
    	void del(TrieNode *curr)
    	{
    		for (int i = 0; i < 26; ++i)
    			if (curr->next[i])
    				del(curr->next[i]);
    		delete curr;
    	}
    public:
    	vector<vector<string>> wordSquares(vector<string>& words) 
    	{
    		if (words.empty()) return res;
    		N = words[0].length();
    		solution.resize(N);
    		root = new TrieNode();
    		for_each(words.begin(), words.end(), [&](string &word) { insert(word); });
    		backtracking(0);
    		del(root);
    		return res;
    	}
    };
    

Log in to reply
 

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