一道百度编程题。

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);&nbsp;if(flag)&nbsp;{return true;&nbsp;}}}return false;}&nbsp;}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);&nbsp;flag=dfs(a_pair,tmp.second);a_pair.insert(a_pair.begin()+i,tmp);&nbsp;if(flag)break;}if(flag)cout<<1;elsecout<<-1;return 0;}