什么是resident alien?# Immigration - 落地生根
a*e
1 楼
写了很久都过不了，15分钟哪里能写完啊？能把思路说清楚就不错了。不知道什么样的
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
vector> res;
vector> empty;
queue curLevel;
queue nextLevel;
vector path;
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bool change = false;
while (!curLevel.empty() || !nextLevel.empty())
{
if (find)
break;
if (curLevel.empty() && !nextLevel.empty())
{
curLevel.swap(nextLevel);
}
word = curLevel.front();
curLevel.pop();
if (word == end)
break;
for (int i = 0; i < n; i++)
{
string tmp = word;
for (int j = 0; j < 26; j++)
{
char tc = 'a' + j;
if (word[i] != tc)
{
tmp[i] = tc;
if (dict.find(tmp) != dict.end() || tmp == end)
{
nextLevel.push(tmp);
if (tmp == end)
{
find = true;
break;
}
dict.erase(tmp);
change = true;
}
}
}
//
if (change)
{
}
}
if (nextLevel.size() > 0)
{
int m = nextLevel.size();
queue tmpNext;
if (m > 1)
{
int oResSize = res.size();
for (int mm = 1; mm < m; mm++)
{
for (int k = 0; k < oResSize; k++)
{
res.insert(res.begin() + k, res[k]);
}
}
}
//res.insert(res.begin(),res.begin(),res.end());
for (int k = 0; k < res.size(); k++)
{
if (res[k].back() == word)
{
string tmp = nextLevel.front();
nextLevel.pop();
res[k].push_back(tmp);
tmpNext.push(tmp);
}
}
nextLevel = tmpNext;
}
}
if (!find) return empty;
else
{
for (int k = 0; k < res.size(); k++)
{
if (res[k].back() != end)
res.erase(res.begin() + k);
}
return res;
}
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector
string> &dict) {
vector
vector
queue
queue
vector
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bool change = false;
while (!curLevel.empty() || !nextLevel.empty())
{
if (find)
break;
if (curLevel.empty() && !nextLevel.empty())
{
curLevel.swap(nextLevel);
}
word = curLevel.front();
curLevel.pop();
if (word == end)
break;
for (int i = 0; i < n; i++)
{
string tmp = word;
for (int j = 0; j < 26; j++)
{
char tc = 'a' + j;
if (word[i] != tc)
{
tmp[i] = tc;
if (dict.find(tmp) != dict.end() || tmp == end)
{
nextLevel.push(tmp);
if (tmp == end)
{
find = true;
break;
}
dict.erase(tmp);
change = true;
}
}
}
//
if (change)
{
}
}
if (nextLevel.size() > 0)
{
int m = nextLevel.size();
queue
if (m > 1)
{
int oResSize = res.size();
for (int mm = 1; mm < m; mm++)
{
for (int k = 0; k < oResSize; k++)
{
res.insert(res.begin() + k, res[k]);
}
}
}
//res.insert(res.begin(),res.begin(),res.end());
for (int k = 0; k < res.size(); k++)
{
if (res[k].back() == word)
{
string tmp = nextLevel.front();
nextLevel.pop();
res[k].push_back(tmp);
tmpNext.push(tmp);
}
}
nextLevel = tmpNext;
}
}
if (!find) return empty;
else
{
for (int k = 0; k < res.size(); k++)
{
if (res[k].back() != end)
res.erase(res.begin() + k);
}
return res;
}
