Word Ladder in Java : Time Limit Exceeded


  • 0
    P

    public static int ladderLength(String start, String end, Set<String> dict) {

    	if(start.equals(end)){
    		return 0;
    	}
    	
    	if(dict.size()==2 && dict.contains(start)&&dict.contains(end))
    		return 2;
    	
    	
    	dict.add(end);
    	int distance = 0;
    	
    	
    	
    	Queue<String> queue = new LinkedList<String>();
    	queue.add(start);
    	
    	StringBuilder word = new StringBuilder();
    	
    	while(!queue.isEmpty()){
    		//char[] word = str.aqueue.poll().toCharArray();
    		word.setLength(0);//clear buffer
    		word.append(queue.poll());
    		++distance;
    		for (int i = 0; i < word.length(); i++) {
    			char backup = word.charAt(i);
    			for (char c='a';c < 'z';c++) {
    				if(word.charAt(i)!=c){
    					//word[i]=c;
    					word.setCharAt(i, c);
    					String tmp = new String(word);
    					if(dict.contains(tmp)){
    						if(tmp.equals(end)){
    							return distance;
    						}else
    						{
    							queue.add(tmp);
    						}
    					}
    				}
    			}
    			//word[i]=backup; //restore character --save memory
    			word.setCharAt(i, backup);
    		}
    	}
    	
    	return 0;
    }

  • 0
    P

    Fixed Above, I was not removing words from Dictionary, which was one reason to go in loop , also optimized it further for memory and runtime

    public static  int ladderLength(String start, String end, Set<String> dict) {
        	
        	if(start.equals(end)){
        		return 0;
        	}
        	
        	int count=0;
        	if(dict.contains(start)&&dict.contains(end))
        		count=2;
        	
        	if(dict.size()==2 && count==2)
        		return 0;
        	
        	if(dict.contains(start))
        		dict.remove(start);
    
        	//dict.add(end);
        	
        	Set<Character> unique = new HashSet<Character>();
        	Iterator<String> itr = dict.iterator();
        	while(itr.hasNext()){
        		String word = itr.next();
        		for (int i = 0; i < word.length(); i++)
        		{
        			unique.add(word.charAt(i));
        		}
        	}
        	Character[] chars =  unique.toArray(new Character[unique.size()]);
      
        	
        	int distance = 1;
        	
        	
        	Queue<String> queue = new LinkedList<String>();
        	queue.add(start);
        	
        	StringBuilder word = new StringBuilder();
        	
        	int currentLevel=1;
        	int nextLevel=0;
        	
        	while(!queue.isEmpty()){
        		word.setLength(0);//clear buffer
        		String t=queue.remove();
        		--currentLevel;
        		word.append(t);
        		
        		for (int i = 0; i < word.length(); i++) {
        			char backup = word.charAt(i);
    				for (int j=0;j<chars.length;j++) {
    					if(word.charAt(i)!=chars[j]){
    						word.setCharAt(i, chars[j]);
    						String tmp = new String(word);
    						if(dict.contains(tmp)){
    							//System.out.println(tmp + " "+distance+ "  ");
    							if(tmp.equals(end)){
    									return ++distance;
    							}else
    							{
    								queue.add(tmp);
    								//nopath=false;
    							}
    							//remove word from dictionary to avoid loops 
    							dict.remove(tmp);
    							++nextLevel;
    						}
    					}
    					word.setCharAt(i, backup);
    				}
    				word.setCharAt(i, backup);
    			}
        		if(currentLevel==0)
        		{
        			++distance;
        			currentLevel=nextLevel; //next level nodes
        			nextLevel = 0; //next level nodes 0
        		}
    
        	}
        	
        	return 0;
        }

Log in to reply
 

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