Memory Limit Exceeded! Here is Java Code. Where is the problem, please?


  • 0
    S

    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
    if(dict.size() == 0)
    return null;

        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        LinkedList<String> wQueue = new LinkedList<String>();
        
        if(!dict.contains(end)){
    	    dict.add(end);
    	}
        
        wQueue.add(start);
        
        while(!wQueue.isEmpty()){
        	String cur = wQueue.pop();
        	
        	if(cur.equals(end)){
        		break;
        	}
        	
        	map.put(cur, new ArrayList<String>());
        	for(int i = 0; i < cur.length(); i++){
        		char cc[] = cur.toCharArray();
        		for(char c = 'a'; c < 'z'; c++){
        			cc[i] = c;
        			String newStr = new String(cc);
        			if(dict.contains(newStr)){
        				wQueue.add(newStr);
        				
        				ArrayList<String> arr = map.get(cur);
        				arr.add(newStr);
        				if(!newStr.equals(end))
        					dict.remove(newStr);
        			}
        		}
        	}
        	
        }
        wQueue.clear();
        
        	// DFS
        ArrayList<String> one = new ArrayList<String>();
        one.add(start);
        DFS(map, res, one, start, end);
        
        return res;
    }
    
    public void DFS(HashMap<String, ArrayList<String>> map, ArrayList<ArrayList<String>> res,
    				ArrayList<String> one, String cur, String end){
    	if(cur.equals(end)){
    		ArrayList<String> temp = new ArrayList<String>(one);
    		res.add(temp);
    		return;
    	}
    	
    	ArrayList<String> arr = map.get(cur);
    	for(int i = 0; i < arr.size(); i++){
    		one.add(arr.get(i));
    		DFS(map, res, one, arr.get(i), end);
    		one.remove(one.size() - 1);
    	}
    }

Log in to reply
 

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