https://leetcode.com/problems/word-ladder/

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

功力退化啊 ……

区区搜索dfs返回值有问题，看到后面提示说是有bfs，吭哧吭哧写那么多

point：

1.step是随着状态变而不是随着while变，这个是记录在每一步的结构体信息中的

2.不一定一定要优先队列，普通的一样可以

3.真的和普通的bfs没多大区别，咋写的这么费劲

class Solution {
public:
    struct node {
        int pos,step;
        node(int apos, int astep) {
            pos = apos;
            step = astep;
        }
    };
    bool comp(string x, string y) {
        if (x.length() != y.length()) 
            return false;
        int cnt = 0;
        for (int i = 0; i < x.length(); i ++) {
            if (x[i] == y[i])
                cnt ++;
        }
        if (cnt == x.length()-1)
            return true;
        return false;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len = wordList.size();
        vector<bool> vis(len, false);
        queue<node> q;
        for (int i = 0; i < wordList.size(); i ++) {
            if (comp(beginWord, wordList[i])) {
                q.push(node(i,1));
                vis[i] = true;
                //break;
            }
        }
        while(!q.empty()) {
            node x = q.front();
            cout<< wordList[x.pos] << x.step << endl;
            if (wordList[x.pos] == endWord)
                return x.step+1;
            q.pop();
            for (int i = 0; i < wordList.size(); i ++) {
                if (vis[i] == false && comp(wordList[x.pos], wordList[i])) {
                    q.push(node(i, x.step + 1));
                    vis[i] = true;
                }
            }
        }
        return 0;
    }
};

 

class Solution {
public:
    struct node {
        int pos,step;
        node(int apos, int astep) {
            pos = apos;
            step = astep;
        }
        friend bool operator <(node a,node b)
        {
            return b.step<a.step;///
        }
    };
    bool comp(string x, string y) {
        if (x.length() != y.length()) 
            return false;
        int cnt = 0;
        for (int i = 0; i < x.length(); i ++) {
            if (x[i] == y[i])
                cnt ++;
        }
        if (cnt == x.length()-1)
            return true;
        return false;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len = wordList.size();
        vector<bool> vis(len, false);
        priority_queue<node> q;
        for (int i = 0; i < wordList.size(); i ++) {
            if (comp(beginWord, wordList[i])) {
                q.push(node(i,1));
                vis[i] = true;
                //break;
            }
        }
        while(!q.empty()) {
            node x = q.top();
            cout<< wordList[x.pos] << x.step << endl;
            if (wordList[x.pos] == endWord)
                return x.step+1;
            q.pop();
            for (int i = 0; i < wordList.size(); i ++) {
                if (vis[i] == false && comp(wordList[x.pos], wordList[i])) {
                    q.push(node(i, x.step + 1));
                    vis[i] = true;
                }
            }
        }
        return 0;
    }
};