求助：一道关于字符串的C++编程题

分别统计26个字母在首位出现的次数 例如h['z'] 表示z出现在首位的次数， t['z']表示z出现在尾部的次数 正常情况是h['z'] = t['z'] 特殊常情况就是排在最前面的字符串的首字符和排在最后面的字符串的尾字符 如果第一个字符串的首字符和最后一个字符串的尾字符相同，就会出现对于26个字符都有 h = t 如果不相同，那么对于第一个字符的首字符 h = t + 1                             对于最后一个字符的尾字符 h + 1 = t                             对于剩下的24个字符 h = t 总结：  1. 对于26个字符的统计都有 h = t 2. 出现两个字符， 一个h + 1 = t, 一个 h = t + 1, 剩下24个都是h = t 上述两种情况都能成功拼接起来

全排列，直到找到首尾想接的排列 优化：如果一个序列前面的部分不首尾想接，则后面不必计算 class Solution { public: bool endToEnd(vector<string> vstr) { // write code here bool flag = false; //标记是否成功 endToEnd(vstr, 0, flag); return flag; } //交换任意两个字符串获取全排列，start：交换开始的下标 void endToEnd(vector<string> &vstr, int start, bool &flag) { int index = 0; //标记该序列首尾不相接开始的地方 if(judge(vstr, index)) { flag = true; return; } if(index < start) //序列前面的部分不首尾想接，则后面不必计算 return; for(int i = start; i < vstr.size()-1 && !flag; ++i) { for(int j = i+1; j < vstr.size() && !flag; ++j) { swap(vstr[i], vstr[j]); endToEnd(vstr, i+1, flag); //交换回来，比如0，1交换后，下次需要0，2交换，0需要归位 swap(vstr[i], vstr[j]); } } } bool judge(vector<string> &vstr, int &index) { for(int i = 1; i < vstr.size(); ++i) if(vstr[i-1].back() != vstr[i].front()) { index = i; return false; } return true; } };

欧拉同路

中兴测试？

//中规中矩地两两比较就行了，速度也不慢。 int scanStr(int num, char **arr) { for (int i=0; i<num-1; i++) { char *str1 = arr[i]; char *str2 = arr[i+1]; if(str1[strlen(str1)-1] == *str2) continue; else { return -1; break; } } return 1; }

求java版本

全排列一个个试，毫无算法。。。复杂度贼高。。 #include<iostream> #include <string> using namespace std; int book[100], num=4, cou=1; char *word[4] = { "ab","bc","cd","bf" }; bool dfs(int num, char ** arr,char tail) {     if (cou == num )         return true;     for (int i = 0; i < num; ++i)//一个个当首单词     {         if (book[i] == 0 && arr[i][0] == tail)         {             book[i] = 1;             cou++;             if (dfs(num, arr, arr[i][strlen(arr[i]) - 1]))                 return true;             book[i] = 0;             cou--;         }     }     return false; } int canArrangeWords(int num, char ** arr) {     if (num == 1)         return 1;     for (int i = 0; i < num; ++i)//一个个当首单词     {         book[i] = 1;         bool zq=dfs(num,arr,arr[i][strlen(arr[i])-1]);         book[i] = 0;         cou = 1;//链子里只有第一个单词了         if (zq)              return 1;     }     return -1; } int  main() {     int res = canArrangeWords(num, word);     cout << res << endl;     system("pause");     return 0; }