Could anyone post AC code in java for this problem ?


  • 0
    W

    My code is BFS traversal, with a queue , and I use a level demarcator to keep track of distance.
    Its along the lines of code posted in this forum, but i don't see a recent AC java code anywhere. Just wondering if anyone has passed this test with java recently ?


  • 0
    C

    I finally got this to run in a quick enough time in java.

    public int ladderLength(String start, String end, Set<String> dict) {
    
        Deque<String> q = new LinkedList<String>();
        Deque<Integer> d = new LinkedList<Integer>();
    
        q.add(start);
        d.add(1);
        int count;
        
        while(!q.isEmpty()) {
            String item = q.pollFirst();
            count = d.pollFirst();
    
            for (int i=0;i<item.length();i++){
                char[] charArray = item.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    charArray[i] = c;
                    String word = new String(charArray);
                    if (word.equals(end)) {
                        return count + 1;
                    } else if (dict.contains(word)) {
                        dict.remove(word);
                        q.add(word);
                        d.add(count + 1);
                    }
                }
            }
    
        }
    
        return 0;
    }
    

    For the longest time I was trying to find all valid moves from one string to the next like this:

    private Set<String> validMoves(String current, Set<String> dict) {
    
        Set<String> moves = new HashSet<String>();
        for(String s : dict) {
            if (oneAway(current, s)) {
                moves.add(s);
            }
        }
    
        return moves;
    }
    
    private boolean oneAway(String s1, String s2) {
    
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int diff = 0;
        for(int i = 0; i<c1.length; i++) {
            if (c1[i] != c2[i]) {
                diff++;
                if (diff >= 2) {
                    break;
                }
            }
        }
    
        return (diff == 1);
    }
    

    But it was just too slow.


Log in to reply
 

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