題目

編寫一個函數，對字符串數組進行排序，將所有變位詞排在相鄰的位置。

思路1：利用sort函數

首先要清楚什么是變位詞。變位詞就是組成的字母相同，但順序不一樣的單詞。 比如：live和evil就是一對變位詞。

在C++中，排序可以通過STL中的sort函數快速實現。sort可以將字符串數組中的字符串按字典序排序。雖然本題中的要求是按照變位詞的準則來排序，我們還是可以調用sort函數，不過要自己實現sort函數中的compare函數。

實現如下。

#include <iostream> #include <algorithm>using namespace std;bool cmp(string s1, string s2){sort(s1.begin(), s1.end()); // 精髓所在sort(s2.begin(),s2.end());return s1 < s2; } int main(){string s[] = {"axyz", "abc", "yzax", "bac", "zyxa", "fg", "gf"};sort(s, s+7, cmp);for(int i=0; i<7; ++i)cout<<s[i]<<endl;return 0; }復制代碼

注釋：

① sort函數

函數形式：C++ sort(first_pointer, first_pointer+n, cmp)

參數解釋： 第一個參數是數組的首地址，一般寫上數組名就可以，因為數組名是一個指針常量。第二個參數相對較好理解，即首地址加上數組的長度n（代表尾地址的下一地址）。最后一個參數是比較函數的名稱（自定義函數cmp），這個比較函數可以不寫，即第三個參數可以缺省，這樣sort會默認按數組升序排序。

函數拓展：cmp比較函數

//情況一：數組排列 int A[100]; bool cmp1(int a, int b)//int為數組數據類型 {return a > b;//降序排列//return a < b;//默認的升序排列 } sort(A, A+100, cmp1);//情況二：結構體排序 Student Stu[100]; bool cmp2(Student a, Student b) {return a.id > b.id;//按照學號降序排列//return a.id < b.id;//按照學號升序排列 } sort(Stu, Stu+100, cmp2);復制代碼

② 注意事項

第一次看到本題，我的直接思路是利用sort函數實現降序，不定義cmp函數，運行結果并不符合要求。這是因為，對string數組利用sort函數直接進行降序排序，是“將字符串數組中的字符串按字典序排序”，string數組中單個string字符串本身并未得到排序，因此無法正確找到“變位詞”。

// 直接利用sort函數排序，運行結果有誤！！ #include <iostream> #include <algorithm> #include <string> using namespace std;bool cmp(string s1, string s2){//sort(s1.begin(), s1.end());//sort(s2.begin(), s2.end());return s1 < s2; } int main(){string s[] = {"axyz", "abc", "yzax", "bac", "zyxa", "fg", "gf"};sort(s, s + 7, cmp);for (int i = 0; i<7; ++i)cout << s[i] << endl;return 0; }運行結果： // 可以看出以上string字符串均按照字典序排序 abc axyz bac fg gf yzax zyxa復制代碼

思路2：哈希表排序

參考文獻

[1]?寫一個函數對字符串數組排序，使所有變位詞都相鄰

[2]?leetcode 相同字母組成的不同單詞歸為一類即所謂的變位詞

[3] 變位詞排序

[4] 變位詞排序

總結

以上是生活随笔為你收集整理的对字符串数组排序，使所有变位词都相邻（C++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。