Time Limit Exceeded? I thought its' complexity is 26*length*n


  • 0
    K
    public String reP(String A,int j,char q){
    	String re;
    	re = A.substring(0, j)+q+A.substring(j+1);
    	return re;
    }
    public int ladderLength(String beginWord, String endWord, Set<String> wordList){
    		if(beginWord.equals(endWord)) return 0;
    		wordList.add(endWord);
    		int length = 0;
    		String orgin,s;
    		ArrayList <String> list = new ArrayList<String>();
    		Queue<String> queue = new LinkedList<String>();
    		Queue<String> nextQueue = new LinkedList<String>();
    		queue.add(beginWord);
    		while(!queue.isEmpty()){
    			length++;
    			while(!queue.isEmpty()){
    			    orgin = queue.poll();
    			    if(orgin.equals(endWord))
    			    	return length;
    				for(int i = 0; i < orgin.length(); i++){
    					s = orgin;
    					for(char j ='a'; j <= 'z';j++){
    						s = reP(s,i,j);
    						if(!list.contains(s)&&wordList.contains(s)){
    							list.add(s);
    							nextQueue.add(s);
    						}
    					}
    				}
    			}
    			queue.addAll(nextQueue);
    			nextQueue.clear();
    		}
    		return 0;
    }

  • 0
    P

    The variable list is implemented as a linked list. Change it to set and it will pass.


  • 0
    A

    Hi there,

    I used the almost the same way as you did and also met the LTE problem. After I analyzed, I think the LTE is caused by the way we build the all possible Strings. In others' passed solutions, they used the String.toCharArray() to build a char array and modify the specific char to generate all the possible Strings. And we used the String.substring().

    After I changed this point, my solution can pass. I hope it helps.


Log in to reply
 

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