# C++ solution using A*, but worse than BFS, can anybody help to improve?

• I try to solve this problem in three ways:

• BFS
• Two-End BFS
• A*

BFS - 204 ms 83.48%

``````class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
wordList.erase(beginWord);
int length = 1;
// BFS
queue<string> bfs;
bfs.push(beginWord);
while(!bfs.empty())
{
auto n = bfs.size();
while(n--)
{
auto front = bfs.front();
bfs.pop();

if(front == endWord)
return length;

for(int i(0); i < front.length(); ++i)
{
char ch = front[i];
for(int j(0); j < 26; ++j)
{
front[i] = 'a' + j;
if(wordList.count(front))
{
bfs.push(front);
wordList.erase(front);
}
}
front[i] = ch;
}
}
length++;
}
return 0;
}
};
``````

Two-End BFS - 44 ms 100%

``````class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
int length = 1;
unordered_set<string> bfs1 = {beginWord};
unordered_set<string> bfs2 = {endWord};

while(bfs1.size())
{
++length;
unordered_set<string> next;

// Expend bfs1
for(auto& word : bfs1)
wordList.erase(word);
for(auto word : bfs1)
{
for(int i(0); i < word.length(); ++i)
{
char ch = word[i];
for(int j(0); j < 26; ++j)
{
word[i] = 'a' + j;
if(!wordList.count(word))
continue;
// bfs1 Meet bfs2
if(bfs2.count(word))
return length;
next.insert(word);
}
word[i] = ch;
}
}
// Expend small side in next time
if(next.size() < bfs2.size())
swap(bfs1, next);
else
{
swap(bfs1, bfs2);
swap(bfs2, next);
}
}
return 0;
}
};
``````

A* - 264 ms 73.55%

``````struct state
{
string str;
int h; // Different between str and endWord
int g; // Current length
int f; // f = h + g

state(string& s, int h, int g)
: str(s), h(h), g(g)
{
f = h + g;
}
};

struct cmp
{
bool operator() (const state& a, const state& b)
{
return a.f > b.f;
}
};

class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
// Compute all word's 'h'
map<string, int> h;
for(auto& word : wordList)
{
int diff = 0;
for(int i(0); i < endWord.length(); ++i)
{
if(word[i] != endWord[i])
++diff;
}
h[word] = diff;
}

// A*
priority_queue<state, vector<state>, cmp> open;
unordered_set<string> openset;

open.push(state(beginWord, 0, 1));
openset.insert(beginWord);
while(!open.empty())
{
auto s = open.top();
open.pop();
openset.erase(s.str);
wordList.erase(s.str);

if(s.str == endWord)
return s.g;

// Try expend current state
auto& word = s.str;
for(int i(0); i < word.length(); ++i)
{
char ch = word[i];
for(char j('a'); j <= 'z'; ++j)
{
word[i] = j;
// Because we inc 'g' only one in every step,
// if the word is already in openset,
// then the word's 'g' must equal or bigger than 'g' in openlist
// and that means we needn't fix 'g' in openlist
if(!wordList.count(word) || openset.count(word))
continue;

open.push(state(word, h[word], s.g + 1));
openset.insert(word);
}
word[i] = ch;
}
}
return 0;
}
};
``````

As we known, BFS is the worst case in A* (h always equals 0). But my A* solution's time cost is worse than BFS. Can anybody help to improve or fix that solution?

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