straightforward BFS, JAVA


  • 1
    S
    class Solution {
        class item {
        int dis;
        String w;
        
        item(int dis, String w){
            this.dis = dis;
            this.w = w;
        }
    }
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            List<item> worditem = new ArrayList<>();
            
             //set distance of start word to be one
            item beginword = new item(1,beginWord);
            worditem.add(beginword);
            
            Iterator<String> itt = wordList.iterator();
                while(itt.hasNext()){
                   item newitem = new item(0,itt.next());
                    worditem.add(newitem);
                }
            
            Queue<item> words = new LinkedList<>();
            words.add(beginword);
            
            while(!words.isEmpty()){
                item curr = words.poll();
                
                Iterator<item> it = worditem.iterator();
                while(it.hasNext()){
                    item temp = it.next();
                    String nextword = temp.w;
                    if(differbyone(curr.w,nextword)){
                        //add dictionary word to queue
                        item temp1 = new item(curr.dis+1,nextword);
                        words.add(temp1);
                        
                        it.remove();
                        
                        if(nextword.equals(endWord)){
                            return temp1.dis;
                            
                        }
                    }
                }
                    
            }
            
            return 0;
        }
        public boolean differbyone(String curr, String next){
            int differ=0;
            for(int i=0;i<curr.length();i++){
                if(curr.charAt(i) != next.charAt(i)){
                    differ++;
                }
                if(differ>1){
                    return false;
                }
            }
            return true;
        }
    }
                       
                      
    
    
    
    
    

Log in to reply
 

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