Can anyone help me?


  • 0
    Z

    My code is like this, I passed 12/14.
    But for a very long test case, it failed. And that's very difficult to debug.
    So what's wrong with this?

    #include <map>
    #include <string>
    using namespace std;
    
    struct Node
    {
    	char c;
    	bool isLeaf;
    	map<char, Node*> index;
    
    	explicit Node(char i)
    	{
    		c = i;
    		isLeaf = false;
    	}
    
    };
    
    class Trie 
    {
    public:
    	/** Initialize your data structure here. */
    	Trie() 
    	{
    		head = new Node('0');
    	}
    
    	/** Inserts a word into the trie. */
    	void insert(string word) 
    	{
    		if (0 == word.length() || search(word))
    			return;
    
    		auto temp = head;
    		for (auto i = 0; i < word.length();++i )
    		{
    			auto c = word[i];
    			auto it = temp->index.find(c);
    			//Check if c is in temp's map
    			if (temp->index.end() == it)//Not found
    			{
    				append(word.substr(i), temp);
    				break;
    			}
    
    			temp = it->second;
    		}
    
    		temp->isLeaf = true;
    
    	}
    
    	/** Returns if the word is in the trie. */
    	bool search(string word) 
    	{
    		auto node = searchInTree(word);
    		return !node || !node->isLeaf ? false : true;
    	}
    
    	/** Returns if there is any word in the trie that starts with the given prefix. */
    	bool startsWith(string prefix)
    	{
    		auto node = searchInTree(prefix);
    		return node;
    	}
    
    private:
    	Node* head;
    
    	/**
    	 * \brief Not found, append to this tree.
    	 * \param remaining 
    	 * \param node father of remaining string.
    	 */
    	void append(string remaining, Node* node)
    	{
    		for (auto c : remaining)
    		{
    			auto newNode = new Node(c);
    			node->index.insert(make_pair(c, newNode));
    			node = newNode;
    		}
    		node->isLeaf = true;
    	}
    
    	Node* searchInTree(string word)
    	{
    		if (0 == word.length())
    			return head;
    
    		auto temp = head;
    		for (auto c : word)
    		{
    			auto it = temp->index.find(c);
    			//Check if c is in temp's map
    			if (temp->index.end() == it)//Not found
    				return nullptr;
    
    			temp = it->second;
    		}
    
    		return temp;
    	}
    
    };
    
    

Log in to reply
 

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