[leetcode BFS] word Solitaire

Title Description

Given two words (beginWord and endWord) and a dictionary, find the length of the shortest conversion sequence from beginWord to endWord. The following rules shall be followed for conversion:

  • Only one letter can be changed per conversion.
  • The intermediate word in the conversion process must be a word in the dictionary.

Description:

  • If no such conversion sequence exists, 0 is returned.
  • All words have the same length.
  • All words consist of lowercase letters only.
  • There are no duplicate words in the dictionary.
  • You can assume that beginWord and endWord are not empty, and they are not the same.

Example:

input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

output: 5

![](https://img2020.cnblogs.com/blog/1617136/202007/1617136-20200712103417745-421529757.png)

explain: A shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     Returns its length 5.

Title Link: https://leetcode-cn.com/problems/word-ladder/

thinking

The title requires that only one letter can be changed per conversion, so we can regard this problem as a search problem, searching a path from the source word to the target word.

Now there is a problem to be solved, that is, how do we judge that two words are adjacent? For example, hit and hot have only one letter, which is adjacent. We can extract the "pattern" of the word by changing one letter of the word each time. For example, we can get: *it, h*t and hi* by changing one letter of "hit" to "*" each time.

For hot, we can also get three modes by doing the same operation: *ot, h*t and ho*. We find that h*t appears in both hit and hot patterns, which indicates that hit can be converted to hot by replacing a letter, which means that hit and hot are adjacent.

Knowing how to define adjacency, we can use bfs to solve it. The steps are as follows:

  • First, according to the words in the dictionary wordList, the mode of each word is calculated and stored in the hash table (unordered_map<string, vector<string>> patterns). For example, patterns['h*t']={"hot","hit"} means that h*t can be converted from hot and hit, and hot and hit are adjacent;
  • Then put the starting word beginWord and the current steps into the queue (you can use pair to encapsulate these two variables to stand up, and the definition of the queue is queue<pair<string, int>> q), marking that beginWord has been accessed;
  • When the queue is not empty, the loop:
    • Get the team header element to get the current word curString and the current path length cnt;
    • Calculate the curString pattern by replacing one letter of curString with * each time, and obtain the next word of curString according to the hash table patterns;
    • If the next word of curString is the target word endWord, then cnt+1 is returned;
    • Otherwise, if the next word of curString has not been accessed, it will queue {curString, cnt+1} and mark that curString has been accessed;
  • If the queue is empty, there is no solution, and 0 is returned;

The codes are as follows:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, vector<string>> patterns;
        for(auto word:wordList){
            for(int i=0; i<word.size(); i++){
                string temp = word;
                temp[i] = '*';
                patterns[temp].push_back(word);
            }
        }
        
        queue<pair<string, int>> q;
        unordered_map<string, bool> visit;  // Mark whether the word has been visited
        q.push(make_pair(beginWord, 1));
        visit[beginWord] = true;
        while(!q.empty()){
            pair<string, int> pr = q.front(); q.pop();
            string curString = pr.first;
            int cnt = pr.second;
            for(int i=0; i<curString.size(); i++){
                string temp = curString;
                temp[i] = '*';
                if(patterns.find(temp)!=patterns.end()){
                    vector<string> candis = patterns[temp];
                    for(string candi:candis){
                        if(candi==endWord) return cnt+1;
                        if(!visit[candi]){
                            q.push(make_pair(candi, cnt+1));
                            visit[candi] =true;
                        }
                    }
                }
            }
        }
        return 0;
    }
};

In fact, instead of using patterns to record patterns, we can directly compare the current word curString with the words in the dictionary wordDict one by one to determine whether the number of different letters is equal to 1. If it is equal to 1 and has not been visited, we can join the queue. This method is relatively easy to think of, and the code will be more concise, but it will time out. The codes are as follows:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<pair<string, int>> q;
        unordered_map<string, bool> visit;  // Mark whether the word has been visited
        q.push(make_pair(beginWord, 1));
        visit[beginWord] = true;
        while(!q.empty()){
            pair<string, int> pr = q.front(); q.pop();
            string curString = pr.first;
            int cnt = pr.second;
            for(auto word:wordList){
                if(visit[word]) continue;
                int diffCnt = 0;
                for(int j=0; j<word.size(); j++){
                    if(curString[j]!=word[j]) diffCnt++;
                }
                if(diffCnt==1 && !visit[word]){
                    if(word==endWord) return cnt+1;
                    q.push(make_pair(word, cnt+1));
                    visit[word] = true;
                }
            }
        }
        return 0;
    }
};
// overtime

Tags: bfs

Posted by cookspyder on Sun, 29 May 2022 23:49:48 +0530