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

• 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) {
Set<String> visited = new HashSet<String>();
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)){
}
}
}
}
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) {
Set<String> visited = new HashSet<String>();
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)){
queue.offer(newWord);
}
}
}

}
level++;
}
return 0;
}
}``````

• 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.

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