Java SOlution with HashMap and single BFS


  • 0
    S
    public class Solution {
        //Declaring variables
        Set<String> mWordList;
        String mBeginWord, mEndWord;
        HashMap<String,Integer> lookup = new HashMap<String,Integer>();
        List<List<String>> myResultList = new ArrayList<List<String>>();
        
        //function to return the solution
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            //Copying into new Hashset because we are removing 
            //elements once they are added into lookup table
            //But we need all elements while printing path
            mWordList = new HashSet<String>(wordList);
            mBeginWord = beginWord;
            mEndWord = endWord;
            fillLookupTable();
            //Copying again because we remove elements form the set 
            //while finding minimum distance
            mWordList = wordList;
            int min = findMin();
            if(min != -1){
                mWordList.remove(mBeginWord);
                List<String> partialResult = new ArrayList<String>();
                partialResult.add(mBeginWord);
                fillResult(partialResult, mBeginWord);
                mWordList.add(mBeginWord);
            }
            return myResultList;
        }
        
        //find the solution
        public void fillLookupTable(){
            lookup.put(mEndWord,0);
            mWordList.remove(mEndWord);
            java.util.LinkedList<String> mQueue = new java.util.LinkedList<String>();
            mQueue.addLast(mEndWord);
            String str = "";
            int min = 0;
            List<String> wordList ;
            while(mQueue.size() > 0){
                str = mQueue.removeFirst();
                min = lookup.get(str) + 1;
                wordList = findOneDistanceWords(str);
                if(wordList!=null){
                    for(String word : wordList){
                        if(!lookup.containsKey(word)){
                            lookup.put(word,min);
                            //once a String is added in lookup table removing 
                            //that string from set, to make the set smaller
                            // so that one distance words can be searched faster
                            mWordList.remove(word);
                            mQueue.addLast(word);
                        }
                    }
                }
            }
        }
        
        //To get the min value of path
        public int findMin(){
            int min = -1 ;
            if(lookup.containsKey(mBeginWord)){
                min = lookup.get(mBeginWord);
            }
            return min;
        }
        
        //To Add solution to arrayList
        public void fillResult(List<String> partialResult, String word){
            int newCopies = 0;
            if(word.equals(mEndWord)){
                myResultList.add(partialResult);
                return;
            }
            List<String> wordList = findOneDistanceWords(word);
            int min = Integer.MAX_VALUE;
            String nextElement = "";
            Integer temp;
            for(String str : wordList){
                temp = lookup.get(str);
                if(temp==null){
                    wordList.remove(str);
                }else{
                    if(temp < min){
                        min = lookup.get(str);
                        newCopies = 0;
                    } else if(temp == min){
                        newCopies++;
                    }
                }
            }
            for(String str : wordList){
                if(lookup.get(str) == min){
                    nextElement = str;
                    mWordList.remove(nextElement);
                    if(newCopies != 0){
                        newCopies--;
                        List<String> copyOfPartialResult = new ArrayList<String>(partialResult);
                        copyOfPartialResult.add(nextElement);
                        fillResult(copyOfPartialResult, nextElement);
                    }else{
                        partialResult.add(nextElement);
                        fillResult(partialResult, nextElement);
                    }
                    mWordList.add(nextElement);
                }
            }
        }
        
        // returns arrayList with all one distance strings from given String
        public List<String> findOneDistanceWords(String word){
             //returns null if cannot find any one Distance word
             List<String> result = null;
             for(String str : mWordList){
                 if(oneDistance(word,str)){
                     if(result==null){
                         result = new ArrayList<String>();
                     }
                     result.add(str);
                 }
             }
             return result;
         }
         
         //returns true if two strings are one distance apart
         public boolean oneDistance(String word1, String word2){
             int unmatched = 0;
             int length = word1.length();
             for(int i = 0 ; i < length ; i++){
                 if(word1.charAt(i) != word2.charAt(i)){
                     unmatched++;
                 }
                 if(unmatched > 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.