一道百度编程题。

Question

将一组单词排列在一个列表，使得列表中任何单词的首字母与其前面单词的尾字母相同。输入一个整数num（单词个数），单词数组char **arr，1<=num<=100，2<=各单词长度<=100，且只包含小写字母。若列表中的单词可按照要求排列，返回1，否则，返回-1。如：a,[abcd,defg,ghij,jkl]输出1

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>

typedef pair<char,char> type;

bool dfs(vector<type> &a, char key)
{
if(a.empty())
{
return true;
}
else
{
int n=a.size();
for(int i=0;i<n;i++)
{
if(a[i].first==key)
{
auto tmp=a[i];
a.erase(a.begin()+i);
auto flag=dfs(a,tmp.second);
a.insert(a.begin()+i,tmp); 
if(flag) 
{
return true; 
}
}
}
return false;
} 
}

int main() {
vector<string> a={"abcd","hkl","dk","kj","jh"};
int n=a.size();

vector<type> a_pair;
for(auto t:a)
{
a_pair.push_back(make_pair(t.front(),t.back()));
}

bool flag=false;
for(int i=0;i<n;i++)
{
auto tmp=a_pair[i];
a_pair.erase(a_pair.begin()+i); 
flag=dfs(a_pair,tmp.second);
a_pair.insert(a_pair.begin()+i,tmp); 
if(flag)
break;
}
if(flag)
cout<<1;
else
cout<<-1;

return 0;
}