Share my easy BFS Solution, JAVA


  • 0

    The idea is not special, the trick here is generating new strings and check the existence, not comparing current string with all elements in the set.

    public class Solution {
        int ret = Integer.MAX_VALUE;
        class myClass{
            String str;
            int step;
            public myClass(String s, int t){
                str = s;
                step = t;
            }
        }
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            int len = beginWord.length();
            Queue<myClass> q = new LinkedList<>();
            Set<String> dict = new HashSet<>();
            q.offer(new myClass(beginWord,1));
            dict.add(beginWord);
            while(!q.isEmpty()){
                String cur = q.peek().str;
                int step = q.poll().step;
                if(cur.equals(endWord)) return step;
                for(int i=0;i<len;i++){
                    for(int j=0;j<26;j++){
                        String next = getNext(cur, i, j);
                        if(wordList.contains(next) && dict.contains(next)==false){
                            q.offer(new myClass(next, step+1));
                            dict.add(next);
                        }
                    }
                }
            }
            return ret==Integer.MAX_VALUE?0:ret;
        }
        public String getNext(String a, int i, int j){
            char[] input = a.toCharArray();
            input[i] = (char)('a'+j);
            return new String(input);
        }
    }
    

  • 0
    C

    Save my code with both BFS and TLE... Thanks!


Log in to reply
 

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