Share my java solution with Tree idea


  • 0
    W

    public class Solution {

    public class myNode {
    	myNode parent;
    	myNode brother;
    	myNode child;
    	String val;
    
    	public myNode(String str) {
    		this.val = str;
    		parent = null;
    		brother = null;
    		child = null;
    	}
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    	List<List<String>> quickRe = new ArrayList<List<String>>();
    	List<String> candList = new ArrayList<String>();
    	 if(isNearWord(start,end)){
    	 candList.add(start);
    	 candList.add(end);
    	 quickRe.add(candList);
    	 return quickRe;
    	 }
    	List<myNode> reList = new ArrayList<myNode>();
    	myNode startNode = new myNode(start);
    	myNode curHeadNode = startNode; // 指向当前层的头结点
    	myNode curNode = startNode; // 指向当前结点
    	dict.remove(startNode.val);
    	while (true) {
    		myNode tmpHead = new myNode("");
    		curNode.child = tmpHead;
    		tmpHead.parent = curNode;
    		List<String> rmList = new ArrayList<String>();
    		while (curNode != null) {
    			List<myNode> nearList = this.findNeadWords(curNode,dict,rmList);
    			
    			if(nearList.size() > 0){
    				tmpHead.brother = nearList.get(0);
    				tmpHead = nearList.get(nearList.size() -1);
    			}
    			curNode = curNode.brother;
    		}
    		dict.removeAll(rmList);
    		
    		curHeadNode = curHeadNode.child.brother;
    		curNode = curHeadNode;
    		boolean isFound = false;
    		List<List<String>> finalReList = new ArrayList<List<String>>();
    		if(curNode == null)
    			return finalReList;
    		while (curNode != null) {
    			//System.out.println("cur found: " + curNode.val);
    			if (curNode.val.equals(end)) {
    				List<String> tmp = new ArrayList<String>();
    				myNode n = curNode;
    				
    				while(n != null){
    					tmp.add(0, n.val);
    					n = n.parent;
    				}
    				finalReList.add(tmp);
    				isFound = true;
    			}
    			curNode = curNode.brother;
    		}
    		if(isFound){
    			return finalReList;
    		}			
    		
    		curNode = curHeadNode;
    		reList.clear();
    	}
    
    }
    
    public List<myNode> findNeadWords(myNode curNode, Set<String> dict, List<String> rmList){
    	
    	List<myNode> list = new ArrayList<myNode>(); 
    	myNode head = new myNode("");
    	list.add(head);
    	//List<String> rmList = new ArrayList<String>();
         char[] chars = curNode.val.toCharArray();   
         for(int j = 0;j < curNode.val.length();j++){   
           char original = chars[j];   
           for(char c = 'a';c <= 'z';c++){   
             chars[j] = c;   
             String t = new String(chars);   
             if(!t.equals(curNode.val) && dict.contains(t)){
            	 myNode tmpNode = new myNode(t);
            	 tmpNode.parent = curNode;
            	 head.brother = tmpNode;
            	 head = head.brother;
            	 list.add(tmpNode);   
            	 rmList.add(t);
             }
           }   
           chars[j] = original;   
         }   
         //dict.removeAll(rmList);
         list.remove(0);
         return list; 
    }
    
    public boolean isNearWord(String start, String curStr) {
    	char[] chSt = start.toCharArray();
    	char[] cur = curStr.toCharArray();
    	int count = 0;
    	for (int i = 0; i < chSt.length; i++) {
    		if (chSt[i] != cur[i]) {
    			count++;
    		}
    	}
    	if (count == 1)
    		return true;
    	else
    		return false;
    }
    

    }


Log in to reply
 

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