C++變位詞問題分析
在《編程珠璣》一書的第二章提到了一個變位詞問題，變位詞指的是一個單詞可以通過改變其他單詞中字母的順序來得到，也叫做兄弟單詞，如army->mary。由變位詞可以引申出幾個算法問題，包括字符串包含問題，比較兩個字符串是否是變位詞，以及找出字典中變位詞集合的問題。
一、字符串包含問題
(1) 問題描述：存在字符串1和字符串2，假設字符串2相對較短，如何快速地判定字符串2中的字符都存在于字符串1里（假定字符串只包含字母）？
(2) 舉例：字符串1為ABCDEFGHIJK，字符串2為ABCDE，則字符串1包含字符串2，因為字符串2中包含的字母在字符串1中也都有。
(3) 解決方案：
思路一
最直接的思路就是針對字符串2中的每個字符，輪詢字符串1進行比較，看是否在字符串1里面。很明顯這種的時間效率為O(n*m)。
/*************************************************************************
> File Name: test.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
void Compare(string long_str, string short_str)
{
int i,j;
for(i=0; i<short_str.size(); ++i)
{
for(j=0; j<long_str.size(); ++j)
{
if(long_str[j] == short_str[i])
{
break;
}
}
if(j == long_str.size())
{
cout << "false" << endl;
return;
}
}
cout << "true" << endl;
return;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEF";
Compare(l, s);
return 0;
}
思路二
這里由于假定了字符串只包含字母，所以我們可以用一個額外的數(shù)組flag[26]作為26個字符標識位，先遍歷長字符串將對應的標識位置1，再遍歷短字符串，如果對應的標示位都是1，則包含；否則不包含。這種方法的時間復雜度為O(n+m)，為了提高空間效率，這里不使用數(shù)組而使用26個bit位來作為標示位（bitset容器）。
/*************************************************************************
> File Name: test1.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<bitset>
#include<string>
using namespace std;
bool Compare(string long_str, string short_str)
{
bitset<26> flag;
for(int i=0; i<long_str.size(); ++i)
{
// flag.set(n)置第n位為1
flag.set(long_str[i]-'A');
}
for(int i=0; i<short_str.size(); ++i)
{
// flag.test(n)判斷第n位是否為1
if(!flag.test(short_str[i]-'A'))
return false;
}
return true;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEZ";
if(Compare(l, s))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
這種方法還可以進行優(yōu)化，例如如果長字串的前綴就為短字串，那么我們可以不需要n+m次，而只需要2m次。具體實現(xiàn)請自己思考。
思路三
給每個字母分配一個素數(shù)，從2開始到3，5，7...遍歷長字串，求得每個字符對應素數(shù)的乘積。然后遍歷短字串，判斷該乘積能否被短字符串中的字符對應的素數(shù)整除，如果除的結果存在余數(shù)，則說明有不匹配的字母；如果整個過程都沒有余數(shù)，則說明短字串中的字母在長字串里都有。這種方法的時間復雜度也是O(n+m)，需要26個額外空間存素數(shù)，但是這種方法有一個缺點就是需要跟大整數(shù)打交道，因為乘積可能非常大。（這里我們使用<cstdint>頭文件中定義的int64_t和uint64_t）
/*************************************************************************
> File Name: test2.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
#include<stdint.h>
//#include<cstdint> // C++11
using namespace std;
bool Compare(string long_str, string short_str)
{
unsigned int primeNum[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101};
/* int64_t和uint64_t分別表示64位的有符號和無符號整形數(shù) */
/* 在不同位數(shù)機器的平臺下通用，都是64位 */
uint64_t ch = 1;
for(int i=0; i<long_str.size(); ++i)
{
ch = ch*primeNum[long_str[i]-'A'];
}
for(int i=0; i<short_str.size(); ++i)
{
if(ch%primeNum[short_str[i]-'A'] != 0)
return false;
}
return true;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEK";
if(Compare(l, s))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
二、比較兩個字符串是否為變位詞
(1) 問題描述：如果兩個字符串的字符一樣，但是順序不一樣，被認為是兄弟字符串，問如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。
(2) 注意：第一點中討論了字符串包含問題，但是不要以為兩個字符串互相包含就是（變位詞）兄弟字符串了，例如aabcde和edcba互相包含，但它們不是變位詞。
(3) 解決方案：
思路一
給每個字母分配一個素數(shù)，可以通過判斷兩個字符串的素數(shù)乘積是否相等。跟上述素數(shù)法一樣，時間復雜度也是O(n+m)，需要跟大整數(shù)打交道。
/*************************************************************************
> File Name: test3.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
#include<stdint.h>
//#include<cstdint> // C++11
using namespace std;
bool Compare(string s1, string s2)
{
unsigned int primeNum[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101};
uint64_t ch = 1;
for(int i=0; i<s1.size(); ++i)
{
ch = ch*primeNum[s1[i]-'a'];
}
for(int i=0; i<s2.size(); ++i)
{
ch = ch/primeNum[s2[i]-'a'];
}
if(ch == 1)
return true;
else
return false;
}
int main()
{
string s1 = "abandon";
string s2 = "banadon";
if(Compare(s1, s2))
cout << "They are brother words!" << endl;
else
cout << "They aren't brother words!" << endl;
return 0;
}
思路二
將兩個字符串按照字母表順序排序，看排序后的字符串是否相等，如果相等則是兄弟字符串（變位詞）。這種方法的時間效率根據(jù)你使用的排序算法不同而不同。當然，你可以自己寫排序算法，這里我們使用C++的STL中的sort()函數(shù)對字符串進行排序。
/*************************************************************************
> File Name: test4.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
// 自定義序函數(shù)（二元謂詞）
bool myfunction(char i, char j)
{
return i > j;
}
bool Compare(string s1, string s2)
{
// 采用泛型算法對s1,s2排序，sort()采用的是快速排序算法
sort(s1.begin(), s1.end(), myfunction);
sort(s2.begin(), s2.end(), myfunction);
if(!s1.compare(s2)) // 相等返回0
return true;
else
return false;
}
int main()
{
string s1 = "abandon";
string s2 = "banadon";
if(Compare(s1, s2))
cout << "They are brother words!" << endl;
else
cout << "They aren't brother words!" << endl;
return 0;
}
三、字典找出所有變位詞集合（重點）
(1) 問題描述：給定一個英語字典，找出其中的所有變位詞集合。
(2) 解決方案：
思路一
對于這個問題，最快想到的最直接的方法就是針對每一個單詞跟字典中的其他單詞進行比較。然而，假設一次比較至少花費1微秒的時間，則擁有二十萬單詞的字典將花費：200000單詞 x 200000比較/單詞 x 1微秒/比較 = 40000x10^6秒 = 40000秒 ≈ 11.1小時。比較的次數(shù)太多了，導致效率低下，我們需要找出效率更高的方法。
思路二
標識字典中的每一個單詞，使得在相同變位詞類中的單詞具有相同的的標識，然后集中具有相同標識的單詞。將每個單詞按照字母表排序，排序后得到的字符串作為該單詞的標識。那么對于該問題的解題過程可以分為三步：第一步，讀入字典文件，對單詞進行排序得到標識；第二步，將所有的單詞按照其標識的順序排序；第三步，將同一個變位詞類中的各個單詞放到同一行中。
這里出現(xiàn)了標識-單詞（key-value）對，我們很容易想到C++中的關聯(lián)容器map，使用map的好處就是：
動態(tài)管理內(nèi)存，容器大小動態(tài)改變；
單詞與它的標識一一對應，對于相同標識(key)的單詞直接加在值(value)后面；
無需根據(jù)標識排序，因為map會自動按關鍵字有序（默認升序）。
所以，在將每個單詞及其標識存入map以后，就可以直接遍歷輸出了，每一個map元素就是一個變位詞集合。
C++實現(xiàn)代碼如下：
/*************************************************************************
> File Name: test5.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<fstream> // file I/O
#include<map> // map
#include<string> // string
#include<algorithm> // sort
using namespace std;
/*
*map是C++中的關聯(lián)容器
* 按關鍵字有序
* 關鍵字不可重復
*/
map<string, string> word;
/* 自定義比較函數(shù)（用于排序） */
bool myfunction(char i, char j)
{
return i < j;
}
/*
*對每個單詞排序
*排序后字符串作為關鍵字，原單詞作為值
*存入map中
*/
void sign_sort(const char* dic)
{
// 文件流
ifstream in(dic);
if(!in)
{
cout << "Couldn't open file: " + string(dic) << endl;
return;
}
string aword;
string asign;
while(in >> aword)
{
asign = aword;
sort(asign.begin(), asign.end(), myfunction);
// 若標識不存在，創(chuàng)建一個新map元素，若存在，加在值后面
word[asign] += aword + " ";
}
in.close();
}
/*
*寫入輸出文件
*/
void write_file(const char* file)
{
ofstream out(file);
if(!out)
{
cout << "Couldn't create file: " + string(file) << endl;
return;
}
map<string, string>::iterator begin = word.begin();
map<string, string>::iterator end = word.end();
while(begin != end)
{
out << begin->second << "\n";
++begin;
}
out.close();
}
int main()
{
string dic;
string outfile;
cout << "Please input dictionary name: ";
cin >> dic;
cout << "Please input output filename: ";
cin >> outfile;
sign_sort(dic.c_str());
write_file(outfile.c_str());
return 0;
}
附：（2012.5.6百度實習筆試題）一個單詞交換字母位置，可得另一個單詞，如army->mary，成為兄弟單詞。提供一個單詞，在字典中找到它的兄弟。描述數(shù)據(jù)結構和查詢過程。
解題思路：如果不允許進行預處理，那么我們只能順序遍歷整個字典，計算每個單詞的標識與給定單詞的標識比較。如果允許進行預處理，我們可以如上述思路二將所有單詞加入一個map，然后輸出關鍵字（給定單詞的標識）對應的值，值中就包含了該單詞的所有兄弟單詞。
相信本文所述實例有助于讀者更好的掌握C++下數(shù)據(jù)結構與算法的實現(xiàn)技巧。
相關文章
函數(shù)模板實質就是參數(shù)化數(shù)據(jù)類型，稱這種編程模式為數(shù)據(jù)類型泛化編程。本文將通過示例來和大家一起了解下C++中函數(shù)模板的定義與使用，需要的可以參考一下2022-09-09
QT獲取時間的類有3個，分別是QDate、QTime、QDateTime,他們屬于QT的network模塊。本文詳細的介紹了這3個模塊的使用，感興趣的可以了解一下2023-04-04
矩陣在計算機圖形學、工程計算中都占有舉足輕重的地位，本文將討論如何將矩陣更有效地存儲在內(nèi)存中，并且能夠方便地提取矩陣中的元素。感興趣的同學可以了解一下2021-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)單詞小幫手,文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
vector直接翻譯過來為向量,在C++中為封裝動態(tài)數(shù)組的容器,且有序,需要的朋友可以參考下2016-05-05
C語言進階輸入輸出重定向與fopen函數(shù)使用示例詳解
這篇文章主要為大家介紹了C語言進階輸入輸出重定向與fopen函數(shù)的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2022-02-02
通過先序遍歷和中序遍歷后的序列還原二叉樹(實現(xiàn)方法)
下面小編就為大家?guī)硪黄ㄟ^先序遍歷和中序遍歷后的序列還原二叉樹(實現(xiàn)方法)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了舉例說明自定義C++異常處理的實例的相關資料,這里舉例說明該如何使用C++ 的異常，需要的朋友可以參考下2017-10-10
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)打開最近文檔功能，并實現(xiàn)基本的新建、打開、保存、退出、幫助等功能，感興趣的可以動手嘗試一下2022-06-06
Opencv實現(xiàn)邊緣檢測與輪廓發(fā)現(xiàn)及繪制輪廓方法詳解
這篇文章主要介紹了Opencv實現(xiàn)邊緣檢測與輪廓發(fā)現(xiàn)及繪制輪廓方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-12-12