Time limit exceeded - using HashSet


  • 0
    S

    I have two solutions, one that uses HashSet and the other that doesn't. I found the time limit exceeded happens when I don't use HashSet for tracking the state. I found the solution, but I don't know why it works. Can you please explain why it works? Thanks in advance.

    This is the code that contains HashSet

    public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start == null || end == null || start.length() != end.length() || start.length() == 0) {
            return 0;
        }
        
        Set<String> visited = new HashSet<String>();
        Queue<String> que = new LinkedList<String>();
        que.add(start);
        
        int depth = 1;
        int CurrentLevel = 1;
        int NextLevel = 0;
        
        while(que.peek() != null) {
            String str = que.poll();
            CurrentLevel--;
            for(int i=0; i<str.length(); i++) {
                char[] test = str.toCharArray();
                for(char j='a'; j<='z'; j++) {
                    test[i] = j;
                    String tmp = new String(test);
                    if(tmp.equals(end)) {
                        return depth+1;
                    }
                    if(!visited.contains(tmp) && dict.contains(tmp)) {
                        que.add(tmp);
                        NextLevel ++;
                        visited.add(tmp);
                    }
                }
            }
            if(CurrentLevel == 0) {
                CurrentLevel = NextLevel;
                NextLevel = 0;
                depth++;
            }
        }
        return 0;
    }
    

    }

    And this is the code that does not contains HashSet

    public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start == null || end == null || start.length() != end.length() || start.length() == 0) {
            return 0;
        }
        
        Queue<String> que = new LinkedList<String>();
        que.add(start);
        
        int depth = 1;
        int CurrentLevel = 1;
        int NextLevel = 0;
        
        while(que.peek() != null) {
            String str = que.poll();
            CurrentLevel--;
            for(int i=0; i<str.length(); i++) {
                char[] test = str.toCharArray();
                for(char j='a'; j<='z'; j++) {
                    test[i] = j;
                    String tmp = new String(test);
                    if(tmp.equals(end)) {
                        return depth+1;
                    }
                    if(dict.contains(tmp)) {
                        que.add(tmp);
                        NextLevel ++;
                    }
                }
            }
            if(CurrentLevel == 0) {
                CurrentLevel = NextLevel;
                NextLevel = 0;
                depth++;
            }
        }
        return 0;
    }
    

    }


Log in to reply
 

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