Why I am getting time limit exceeded issue for word ladder problem?


  • 0
    I
    public class Solution {
        
        public class Ladder{
            private int length;
            private String lastWord;
    
            public Ladder(int length, String lastWord){
                this.length = length;
                this.lastWord = lastWord;
    
            }
    
            public int getLength(){
                return this.length;
            }
            public void setLength(int length){
                this.length = length;
            }
    
            public String getLastWord(){
                return this.lastWord;
            }
            public void setLastWord(String lastWord){
                this.lastWord = lastWord;
            }
    
    
        }
    
        public boolean checkDifferByOne(String first, String second){
            int length = first.length();
            int value = 1;
            boolean oneAllowed = false;
            for(int i = 0; i < length; i++){
    
                if(oneAllowed && Math.abs(first.charAt(i) - second.charAt(i)) > 0){
                    return false;
                }
    
                if(Math.abs(first.charAt(i) - second.charAt(i)) > 0){
                    oneAllowed = true;
                }
    
            }
            return true;
        }
    
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    
            wordList.add(beginWord);
            wordList.add(endWord);
    
            if(beginWord.equals(endWord)){
                return 1;
            }
    
            Queue<Ladder> queue = new LinkedList<Ladder>();
            List<String> path = new LinkedList<String>();
            path.add(beginWord);
            queue.add(new Ladder(1, beginWord));
            wordList.remove(beginWord);
    
    
            while(!queue.isEmpty() && !queue.peek().equals(endWord)){
    
                Ladder ladder = queue.remove();
                if(ladder.getLastWord().equals(endWord)){
                    return ladder.getLength();
                }
    
                Iterator<String> it = wordList.iterator();
                while(it.hasNext()){
                    //System.out.println(queue);
                    String word = it.next();
                    boolean cond = checkDifferByOne(word, ladder.getLastWord());
                    if(cond){
                        //path = new LinkedList(ladder.getPath());
                        path.add(word);
                        queue.add(new Ladder(ladder.getLength() + 1, word));
                        it.remove();
                    }
                }
            }
            if(!queue.isEmpty()){
                //System.out.println(queue.peek().getPath());
                return queue.peek().getLength();
            }
            return 0;
    
        }
        
    }

  • 0
    I

    It's giving time limit exceeded for the big input "nanny", "aloud", "ricky","grind","cubic","panic","lover","farce","gofer","sales","flint", ....
    But when I execute in my intellij, It's running perfectly fine.


Log in to reply
 

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