Why time limit exceeded ? (which solution is better 1 or 2 ) ?


  • 0
    T

    Hi,

    My both solutions (solution1 and solution2) works fine (tested in Eclipse) but OJ gives time limit exceeded exception for solution1.
    Solution2 is accepted.

    I believe solution1 is MORE EFFICIENT than solution2. Isn't it ?

    which one is better in terms of performance ? any advice. Thanks.

    Solution 1:

    public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        visited.add(beginWord);
        queue.add(beginWord);
        int level = 2;
        while(!queue.isEmpty()){
            int qsize = queue.size();
            for(int i=0;i<qsize;i++){
                String word = queue.poll();
                if(isPossible(word, endWord)){
                    return level;
                }
                else {
                    for(String newWord: wordList){
                        if(!visited.contains(newWord) && isPossible(word, newWord)){
                            visited.add(newWord);
                            queue.add(newWord);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
    
    
    public boolean isPossible(String first, String second){
        if(first == null || first.length() == 0 || second == null || second.length() ==0 || first.length() != second.length()){
            return false;
        }
        int count=0;
        for(int i=0;i<first.length();i++){
            if(first.charAt(i) != second.charAt(i)){
                count++;
                if(count > 1){
                    return false;
                }
            }
        }
        return true;
    }
    }
    

    Solution 2:

    public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        visited.add(beginWord);
        queue.add(beginWord);
        int level = 1;
        while(!queue.isEmpty()){
            int qsize = queue.size();
            for(int i=0;i<qsize;i++){
                String word = queue.poll();
                
                for(int j=0;j<word.length();j++){
                    char[] chars = word.toCharArray();
                    for(char letter='a'; letter<='z'; letter++){
                        chars[j] = letter;
                        String newWord = String.valueOf(chars);
                        
                        if(newWord.equals(endWord)) {
                            return level+1;
                        }
                        
                        if(!visited.contains(newWord) && wordList.contains(newWord)){
                            visited.add(newWord);
                            queue.offer(newWord);
                        }
                    }
                }
                
            }
            level++;
        }
        return 0;
    }
    }

  • 2
    W

    Apparently, solution 2 is better than 1.

    In your solution 1, you tried to explored those possible next ladder words from word list, the time complexity is O(n), n is the size of word list;

    In your solution 2, you generated all next ladder words and check if they are in word list or not. the time complexity is O(k) in which k is the word length regardless the nested for loop. I can image the size of word list is much larger than length of words.


Log in to reply
 

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