It's disgusting, It's inefficient, It passed. Need help optimizing (C++ Trie and Recursion)


  • 0
    L
    class Solution {
    public:
        	struct TrieNode {
    
    		char nodeChar = NULL;
    		map<char, TrieNode> children;
    
    		TrieNode() {}
    		TrieNode(char c) { nodeChar = c; }
    	};
    
    
    	struct Trie {
    		TrieNode *root = new TrieNode();
    		typedef pair<char, TrieNode> letter;
    		typedef map<char, TrieNode>::iterator it;
    
    		Trie() {};
    
    		Trie(vector<string> dictionary) {
    			for (int i = 0; i < dictionary.size(); i++) {
    				insert(dictionary[i]);
    			}
    		}
    
    		void insert(string toInsert) {
    			TrieNode * curr = root;
    			int increment = 0;
    			// while letters still exist within the trie traverse through the trie
    			while (curr->children.find(toInsert[increment]) != curr->children.end()) { //letter found
    				curr = &(curr->children.find(toInsert[increment])->second);
    				increment++;
    			}
    			//when it doesn't exist we know that this will be a new branch 
    			for (int i = increment; i < toInsert.length(); i++) {
    				TrieNode temp(toInsert[i]);
    				curr->children.insert(letter(toInsert[i], temp));
    				curr = &(curr->children.find(toInsert[i])->second);
    				if (i == toInsert.length() - 1) {
    					temp.nodeChar = NULL;
    					curr->children.insert(letter(NULL, temp));
    				}
    
    			}
    		}
    
    
    		bool find(string word) {
    			TrieNode * curr = root;
    			for (int i = 0; i < word.length(); i++) {
    				if (curr->children.find(word[i]) == curr->children.end()) {//if current letter doesn't exists
    					return false;
    				}
    				else {
    					curr = &(curr->children.find(word[i])->second);
    					if (i == word.length() - 1) {
    						if (curr->children.find(NULL) != curr->children.end()) { return true; }
    						else { return false; }
    					}
    				}
    			}
    		}
    
    
    
    		vector<string> findPre(string pre) {
    			vector<string> list;
    			TrieNode * curr = root;
    			/*First find if the pre actually exist*/
    			for (int i = 0; i < pre.length(); i++) {
    				if (curr->children.find(pre[i]) == curr->children.end()) { //DNE
    					return list;
    				}
    				else {
    					curr = &(curr->children.find(pre[i])->second);
    				}
    			}
    			/*Now curr is at the end of the prefix, now we will perform a DFS*/
    
    			pre = pre.substr(0, pre.length() - 1);
    			findPre(list, curr, pre);
    
    			return list;
    		}
    
    		void findPre(vector<string> &list, TrieNode *curr, string prefix) {
    			if (curr->nodeChar == NULL) {
    				list.push_back(prefix);
    				return;
    			}
    			else {
    				prefix += curr->nodeChar;
    				for (it i = curr->children.begin(); i != curr->children.end(); i++) {
    					findPre(list, &i->second, prefix);
    				}
    		
    			}
    		}
    
    	};
    
    
    	vector<vector<string>> total;
    	Trie dict;
    
    	//the amount of words will also be the position we need to find the next string
    	string find(vector<string> square) {
    		string temp;
    		for (int i = 0; i < square.size();i++) {
    			temp += square[i][square.size()];
    		}
    		return temp;
    	}
    
    	void wordSquares(vector<string> square, string curr) {
    		square.push_back(curr);
    		if (square.size() == curr.length()) {
    			total.push_back(square);
    			return;
    
    		}
    		vector<string> options = dict.findPre(find(square));
    		if (options.empty()) { return; }
    		for (int i = 0; i < options.size(); i++) {
    			wordSquares(square, options[i]);
    		}
    
    	}
    
    	vector<vector<string>> wordSquares(vector<string>& words) {
    		Trie temp(words);
    		dict = temp;
    		vector<string> square;
    		for (int i = 0; i < words.size(); i++) {
    			wordSquares(square, words[i]);
    			
    		}
    		return total;
    	}
    };
    

Log in to reply
 

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