Why run error with case "hot", "dog", ["hot","dog","dot"]?


  • -1
    S

    Can anybody help me check what is wrong? comments are stated in the code.

    typedef struct MultiWay_Node
    {
    struct MultiWay_Node* father;
    vector<MultiWay_Node*> children;
    string key;
    int num_children;

    MultiWay_Node(string key){
    	this->key = key;
    	this->father=NULL;
    	this->num_children = 0;
    }
    

    }
    MultiWay_Node,*MultiWay_Tree;

    class Solution {
    private:
    map<string,bool> flags;
    //用来保存每一个有效路径的end关键字对应的节点指针
    vector<MultiWay_Node*> effective_endNode;
    //多叉树
    MultiWay_Tree tree;

    public:
    //notice : 两个字符串的长度相等
    bool hasOneDiffChar(string str_a,string str_b){
    int length = str_a.size();
    int count = 0;
    for (int i = 0;i < length;i++)
    {
    if (str_a[i] != str_b[i])
    count++;
    if (count >= 2)
    return false;
    }
    if (count == 0) return false;
    return true;
    }

    void buildMultiWayTree(MultiWay_Tree tree,string end,unordered_set<string> dict){
    	queue<MultiWay_Node*> ready_queue;
    	ready_queue.push(tree);
    	string candidate;
    	MultiWay_Node * p = NULL;
    	MultiWay_Node* q = NULL;
    	unordered_set<string>::iterator iterator;
    	while(!ready_queue.empty()){
    		p = ready_queue.front();
    		if ((p->key).compare(end) != 0)
    		{
    			for (iterator=dict.begin(); iterator != dict.end();iterator++)
    			{
    				candidate = *iterator;
    				if (flags[candidate] == false && hasOneDiffChar(candidate,p->key))
    				{
    					q = new MultiWay_Node(candidate);
    					q->father = p;
    					p->children.push_back(q);
    					p->num_children ++;
    					if (candidate.compare(end) != 0){
    						flags[candidate] = true;
    						ready_queue.push(q);
    					}
    					else{
    						//用来最后从底至上进行遍历之用
    						effective_endNode.push_back(q);					
    					}
    				}
    			}
    			ready_queue.pop();
    		}else
    			ready_queue.pop();
    	}
    }
    
    void getShorttestPath(vector<vector<string>>* result){
    	int edge_length = INT_MAX;
    	vector<string> temp_vector;
    	int paths = effective_endNode.size();
    	int edge_count = 0;
    	MultiWay_Node* p = NULL;
    	for (int i = 0;i < paths;i ++)
    	{
    		edge_count = 0;
    		p = effective_endNode[i];
    		temp_vector.clear();
    		while (p->father != NULL)
    		{
    			edge_count++;
    			temp_vector.push_back(p->key);
    			p = p->father;
    		}
    		temp_vector.push_back(p->key);
    		if (edge_count < edge_length)
    		{
    			result->clear();
    			edge_length = edge_count;
    			reverse(temp_vector.begin(),temp_vector.end());
    			result->push_back(temp_vector);
    		}else if (edge_count == edge_length)
    		{
    			reverse(temp_vector.begin(),temp_vector.end());
    			result->push_back(temp_vector);
    		}else{
    			continue;
    		}
    	}
    }
    
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
    	vector<vector<string>> result;			
    
    	if (start.compare("")==0 || end.compare("")==0 || dict.empty())
    	{
    		return result;
    	}
    
    	//如果end就在dict中呢
    	/**
    	unordered_set<string>::const_iterator findIt = dict.find(end);
    	if (findIt != dict.end())
    	{
    		vector<string> v;
    		v.push_back(start);
    		v.push_back(end);
    		result.push_back(v);
    		return result;
    	}**/
    
    	/**宽度优先(BFS),构建多叉树**/
    	tree = new MultiWay_Node(start);
    	flags[start] = true;
    	//将end压入到字典中
    	dict.insert(end);
    	//调用构建多叉树的函数
    	buildMultiWayTree(tree,end,dict);
    
    	/**从底至上的,深度优先(DFS)遍历多叉树**/
    	if (!effective_endNode.empty())
    	{
    		getShorttestPath(&result);
    	}
    	return result;
    }
    
    void delete_treeNode(MultiWay_Tree tree){
    	if (tree != NULL)
    	{
    		int num_children = tree->num_children;
    		if (num_children == 0)
    		{
    			tree->father->num_children --;
    			tree->father = NULL;
    			delete tree;
    		}else{
    			int len = tree->children.size();
    			for (int i = 0;i < len;i++)
    			{
    				delete_treeNode(tree->children[i]);
    			}
    		}
    	}
    }
    
    ~Solution(){
    	delete_treeNode(tree);
    }
    

    };


Log in to reply
 

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