C++ very easy read and understand solution compared to most voted!


  • 3
    R

    For the most voted solution, it is very complicated.
    I do a BFS for each path
    for example:
    {hit} ->
    {hit,hot} ->
    {hit,hot,dot}/{hit,hot,lot} ->
    ["hit","hot","dot","dog"]/["hit","hot","lot","log"] ->
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]

    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            vector<vector<string>> res;
            unordered_set<string> visit;  //notice we need to clear visited word in list after finish this level of BFS
            queue<vector<string>> q;
            unordered_set<string> wordlist(wordList.begin(),wordList.end());
            q.push({beginWord});
            bool flag= false; //to see if we find shortest path
            while(!q.empty()){
                int size= q.size();
                for(int i=0;i<size;i++){            //for this level
                    vector<string> cur = q.front();
                    q.pop();
                    vector<string> newadd =  addWord(cur.back(),wordlist); 
                    for(int j=0;j<newadd.size();j++){   //add a word into path
                        vector<string> newline(cur.begin(),cur.end());
                        newline.push_back(newadd[j]);
                        if(newadd[j]==endWord){       
                         flag=true;
                        res.push_back(newline);
                        }
                        visit.insert(newadd[j]);
                        q.push(newline);
                    }
                }
                if(flag) break;  //do not BFS further 
                for(auto it=visit.begin();it!=visit.end();it++) wordlist.erase(*it); //erase visited one 
                visit.clear();
            }
            return res;
        }
        
        // find words with one char different in dict
        // hot->[dot,lot]
        vector<string> addWord( string word,unordered_set<string>& wordlist ){
            vector<string> res;
            for(int i=0;i<word.size();i++){
                char s =word[i];
                for(char c='a';c<='z';c++){
                    word[i]=c;
                    if(wordlist.count(word)) res.push_back(word);
                }
                word[i]=s;
            }
            return res;
        }
    };
    

  • 1
    B

    666
    This solution is very 6.


  • 0
    Q

    Nice solution, I rewrite a concise Java version based on yours:

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> res = new ArrayList<>();
            Queue<List<String>> queue = new LinkedList<>();
            queue.offer(new ArrayList<>(Arrays.asList(beginWord)));
            Set<String> visited = new HashSet<>();
            Set<String> word_list = new HashSet<>(wordList);
            boolean found = false;
            if (!word_list.contains(endWord)) return res;
            while (!queue.isEmpty() && !word_list.isEmpty()) {
                for (int i = queue.size(); i > 0; --i) {
                    List<String> path = queue.poll();
                    String back_word = path.get(path.size() - 1);
                    for (int j = 0; j < back_word.length(); j++) {
                        char[] chs = back_word.toCharArray();
                        for (char c = 'a'; c <= 'z'; c++) {
                            if (chs[j] == c) continue;
                            chs[j] = c;
                            String next_word = String.valueOf(chs);
                            if (next_word.equals(endWord)) {
                                path.add(next_word);
                                res.add(path);
                                found = true;
                            }
                            if (word_list.contains(next_word)) {
                                visited.add(next_word);
                                List<String> new_path = new ArrayList<>(path);
                                new_path.add(next_word);
                                queue.offer(new_path);
                            }
                        }
                    }
                }
                if (found) break;
                word_list.removeAll(visited);
                visited.clear();
            }
            return res;
        }
    }
    

  • 0

  • 0
    Z

    I have tried many solutions. This is the only one pass the Leetcode. 6666666666


Log in to reply
 

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