#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <unordered_set>
#define debug(a) { cout<< #a << " " << a << " " ;}
using namespace std;
bool onedist(const string &a, const string &b);
int dfs(string &begin, string &end, unordered_set<string>& words, bool visited[],int &counting);
int ladderLength(string begin, string end, unordered_set<string>& words);
// Function that returns true if the two strings are at an edit distance of 1 from each other
bool onedist(const string &a, const string &b) {
int mismatch = 0;
for(int i = 0;i< a.size(); i++) {
if(a[i] == b[i])
{
// do nothing
}
else mismatch++;
if (mismatch > 1)
return false;
}
return true;
}
int dfs(string &begin, string &end, vector<string>& wordlife, bool visited[],int counting) {
//cout << "begin" << begin <<endl;
if(onedist(begin,end)) {
return counting+1;
// Should exit, but doesn't. Causing run time error
}
int n = wordlife.size();
int c=0,min=n+1;//min is used to find minimum possible transformations required
for(int i = 0;i<n;i++)
{
if(!visited[i] && onedist(begin, wordlife[i])) {
visited[i] = true;
c=dfs(wordlife[i],end,wordlife,visited,counting+1);//we store the value returned by dfs in c so that we can find minimum required transformation
//cout << "Test flow" << c << endl;
if(c<min)
min=c;//to find minimum transformations required
}
}
if(c!=0)
return min; //return min possible transformations
else
return 0;//if no possible transformations are possible
}
int ladderLength(string begin, string end, vector<string>& wordlife)
{
int n = wordlife.size();
bool visited[n];
for(int i = 0;i<n;i++)
visited[i] = false;
int count = 1;
int ans = dfs(begin,end,wordlife,visited,count);
return ans;
}
int main()
{
string begin = "hit";
string end = "cog";
vector<string> wordlife;
wordlife.push_back("hot");
wordlife.push_back("dot");
wordlife.push_back("dog");
wordlife.push_back("lot");
wordlife.push_back("log");
int a = ladderLength( begin, end, wordlife);
cout <<a<<endl;
return 0;//the run time error was because you were returning 'a' instead of 0
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4KI2RlZmluZSBkZWJ1ZyhhKSB7IGNvdXQ8PCAjYSA8PCAiICAiIDw8IGEgPDwgIiAiIDt9CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIG9uZWRpc3QoY29uc3Qgc3RyaW5nICZhLCBjb25zdCBzdHJpbmcgJmIpOwppbnQgZGZzKHN0cmluZyAmYmVnaW4sIHN0cmluZyAmZW5kLCB1bm9yZGVyZWRfc2V0PHN0cmluZz4mIHdvcmRzLCBib29sIHZpc2l0ZWRbXSxpbnQgJmNvdW50aW5nKTsKaW50IGxhZGRlckxlbmd0aChzdHJpbmcgYmVnaW4sIHN0cmluZyBlbmQsIHVub3JkZXJlZF9zZXQ8c3RyaW5nPiYgd29yZHMpOwoKLy8gRnVuY3Rpb24gdGhhdCByZXR1cm5zIHRydWUgaWYgdGhlIHR3byBzdHJpbmdzIGFyZSBhdCBhbiBlZGl0IGRpc3RhbmNlIG9mIDEgZnJvbSBlYWNoIG90aGVyCmJvb2wgb25lZGlzdChjb25zdCBzdHJpbmcgJmEsIGNvbnN0IHN0cmluZyAmYikgewogICAgICAgIGludCBtaXNtYXRjaCA9IDA7CiAgICAgICAgZm9yKGludCBpID0gMDtpPCBhLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgIGlmKGFbaV0gPT0gYltpXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgLy8gZG8gbm90aGluZwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgbWlzbWF0Y2grKzsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmIChtaXNtYXRjaCA+IDEpCiAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgCiAgICBpbnQgZGZzKHN0cmluZyAmYmVnaW4sIHN0cmluZyAmZW5kLCB2ZWN0b3I8c3RyaW5nPiYgd29yZGxpZmUsIGJvb2wgdmlzaXRlZFtdLGludCBjb3VudGluZykgewogICAgICAgLy9jb3V0IDw8ICJiZWdpbiIgPDwgYmVnaW4gPDxlbmRsOwogICAgICAgIGlmKG9uZWRpc3QoYmVnaW4sZW5kKSkgewoKICAgICAgICAgICAgcmV0dXJuIGNvdW50aW5nKzE7IAogICAgICAgICAgICAvLyBTaG91bGQgZXhpdCwgYnV0IGRvZXNuJ3QuIENhdXNpbmcgcnVuIHRpbWUgZXJyb3IKICAgICAgICB9CgogICAgICAgIGludCBuID0gd29yZGxpZmUuc2l6ZSgpOwogICAgICAgIGludCBjPTAsbWluPW4rMTsvL21pbiBpcyB1c2VkIHRvIGZpbmQgbWluaW11bSBwb3NzaWJsZSB0cmFuc2Zvcm1hdGlvbnMgcmVxdWlyZWQKICAgICAgICBmb3IoaW50IGkgPSAwO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBpZighdmlzaXRlZFtpXSAmJiBvbmVkaXN0KGJlZ2luLCB3b3JkbGlmZVtpXSkpIHsKICAgICAgICAgICAgCXZpc2l0ZWRbaV0gPSB0cnVlOwogICAgICAgICAgICAgICAgIGM9ZGZzKHdvcmRsaWZlW2ldLGVuZCx3b3JkbGlmZSx2aXNpdGVkLGNvdW50aW5nKzEpOy8vd2Ugc3RvcmUgdGhlIHZhbHVlIHJldHVybmVkIGJ5IGRmcyBpbiBjIHNvIHRoYXQgd2UgY2FuIGZpbmQgbWluaW11bSByZXF1aXJlZCB0cmFuc2Zvcm1hdGlvbgogICAgICAgICAgICAgICAgIC8vY291dCA8PCAiVGVzdCBmbG93IiA8PCBjIDw8IGVuZGw7CiAgICAgICAgICAgICAgICAgaWYoYzxtaW4pCiAgICAgICAgICAgICAgICAgbWluPWM7Ly90byBmaW5kIG1pbmltdW0gdHJhbnNmb3JtYXRpb25zIHJlcXVpcmVkCiAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICAgICAKICAgICAgICB9CiAgICAgICAgaWYoYyE9MCkKICAgICAgICByZXR1cm4gbWluOyAvL3JldHVybiBtaW4gcG9zc2libGUgdHJhbnNmb3JtYXRpb25zCiAgICAgICAgIGVsc2UKICAgICAgICAgcmV0dXJuIDA7Ly9pZiBubyBwb3NzaWJsZSB0cmFuc2Zvcm1hdGlvbnMgYXJlIHBvc3NpYmxlCiAgICB9CiAgICAKICAgIGludCBsYWRkZXJMZW5ndGgoc3RyaW5nIGJlZ2luLCBzdHJpbmcgZW5kLCB2ZWN0b3I8c3RyaW5nPiYgd29yZGxpZmUpCiAgICB7CiAgICAgICAgCiAgICAgICAgaW50IG4gPSB3b3JkbGlmZS5zaXplKCk7CiAgICAgICAgYm9vbCB2aXNpdGVkW25dOwogICAgICAgIGZvcihpbnQgaSA9IDA7aTxuO2krKykKICAgICAgICAgICAgdmlzaXRlZFtpXSA9IGZhbHNlOwogICAgICAgIGludCBjb3VudCA9IDE7CiAgICAgICAgICAgIAogICAgICAgIGludCBhbnMgPSBkZnMoYmVnaW4sZW5kLHdvcmRsaWZlLHZpc2l0ZWQsY291bnQpOwogICAgICAgIAogICAgICAgIHJldHVybiBhbnM7CiAgICAgICAgCiAgICAgICAgCiAgICAgICAgCiAgICB9CiAgICAKICAgIGludCBtYWluKCkKICAgIHsKICAgIAlzdHJpbmcgYmVnaW4gPSAiaGl0IjsKICAgIAlzdHJpbmcgZW5kID0gImNvZyI7CiAgICAJdmVjdG9yPHN0cmluZz4gd29yZGxpZmU7CiAgICAJd29yZGxpZmUucHVzaF9iYWNrKCJob3QiKTsKICAgIAl3b3JkbGlmZS5wdXNoX2JhY2soImRvdCIpOwogICAgCXdvcmRsaWZlLnB1c2hfYmFjaygiZG9nIik7CiAgICAJd29yZGxpZmUucHVzaF9iYWNrKCJsb3QiKTsKICAgIAl3b3JkbGlmZS5wdXNoX2JhY2soImxvZyIpOwogICAgCWludCBhID0gbGFkZGVyTGVuZ3RoKCBiZWdpbiwgIGVuZCwgIHdvcmRsaWZlKTsKICAgIAljb3V0IDw8YTw8ZW5kbDsKICAgIAlyZXR1cm4gMDsvL3RoZSBydW4gdGltZSBlcnJvciB3YXMgYmVjYXVzZSB5b3Ugd2VyZSByZXR1cm5pbmcgJ2EnIGluc3RlYWQgb2YgMAogICAgfQ==