My algorithm's output is [], but leetcode give me [["a","c"]]


  • 0
    B

    input is : start:"hot" end:"dog" String[] dict = {"hot","dog"};

    output in my system is : []
    but the result run on the leetcode is :[["a","c"]]

    help me ~ thanks

    import java.util.*;

    public class Solution {

    private static ArrayList<Node> so = new ArrayList<Solution.Node>();
    private static int mindeep = 10000;
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    	List<List<String>> result = new ArrayList<List<String>>();
        Node root = new Node();
        root.setValue(start);
        Solution s = new Solution();
        s.subLadders(root, dict, end,1,s);
        for(Node child : Solution.so){
        	if(child.getDeep() == Solution.mindeep){
        		List<String> aresult = new ArrayList<String>();
        		Node p = child;
        		if(p.getValue().equals("a")) return result;
        		aresult.add(p.getValue());
        		while((p=p.getParent()) != null){
        			aresult.add(0,p.getValue());
        		}
        		result.add(aresult);
        	}
        }
        return result;
    }
    
    public void subLadders(Node root, Set<String> dict, String endS, int deep, Solution s){
    	if(deep>Solution.mindeep) return;
    	if(Solution.difference(root.getValue(), endS) == 1){
    		Node childNode = new Node();
    		childNode.setValue(endS);
    		childNode.setParent(root);
    		childNode.setDeep(deep);
    		if(deep<=Solution.mindeep){
    			Solution.mindeep = deep;
    			Solution.so.add(childNode);
    		}
    		return;
    	}
    	for (String aword : dict) {
    		if(Solution.difference(root.value, aword) == 1){
    			Node childNode = new Node();
    			childNode.setValue(aword);
    			childNode.setParent(root);
    			root.addChild(childNode);
    		}
    	}
    	if(root.getChildren().size() == 0){
    		return;
    	}
    	for (Node achild : root.getChildren()) {
    		Set<String> subdict = new HashSet<String>();
    		for(String aword : dict){
    			if(achild.getValue().equals(aword)) continue;
    			subdict.add(aword);
    		}
    		s.subLadders(achild, subdict,endS,deep+1,s);
    	}
    }
    
    public static int difference(String s1, String s2){
    	int d = 0;
    	for(int i=0; i<s1.length(); i++){
    		if(s1.charAt(i) != s2.charAt(i)) d++;
    	}
    	return d;
    }
    public class Node{
    	private int deep = -1;
    	private Node parent;
    	private String value;
    	private ArrayList<Node> children = new ArrayList<Node>();
    	
    	public String getValue(){
    		return this.value;
    	}
    	
    	public void setValue(String avalue){
    		this.value = avalue;
    	}
    	
    	public int getDeep(){
    		return this.deep;
    	}
    	
    	public void setDeep(int adeep){
    		this.deep = adeep;
    	}
    	
    	public Node getParent(){
    		return this.parent;
    	}
    	
    	public void setParent(Node p){
    		this.parent = p;
    	}
    	
    	public void addChild(Node achild){
    		this.children.add(achild);
    	}
    	
    	public ArrayList<Node> getChildren(){
    		return this.children;
    	}
    }
    public static void main(String[] args) {
    	String start = "hot";
    	String end = "dog";
    	String[] adict = {"hot","dog"};
    	Set<String> dict = new HashSet<String>();
    	for (String astring : adict) {
    		dict.add(astring);
    	}
    	Solution s = new Solution();
    	for(List<String> alist: s.findLadders(start, end, dict)){
    		for (String astring : alist) {
    			System.out.print(astring+" ");
    		}
    		System.out.println();
    	}
    }
    

    }


Log in to reply
 

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