C++變位詞問題分析
在《編程珠璣》一書的第二章提到了一個(gè)變位詞問題，變位詞指的是一個(gè)單詞可以通過改變其他單詞中字母的順序來得到，也叫做兄弟單詞，如army->mary。由變位詞可以引申出幾個(gè)算法問題，包括字符串包含問題，比較兩個(gè)字符串是否是變位詞，以及找出字典中變位詞集合的問題。
一、字符串包含問題
(1) 問題描述：存在字符串1和字符串2，假設(shè)字符串2相對(duì)較短，如何快速地判定字符串2中的字符都存在于字符串1里（假定字符串只包含字母）？
(2) 舉例：字符串1為ABCDEFGHIJK，字符串2為ABCDE，則字符串1包含字符串2，因?yàn)樽址?中包含的字母在字符串1中也都有。
(3) 解決方案：
思路一
最直接的思路就是針對(duì)字符串2中的每個(gè)字符，輪詢字符串1進(jìn)行比較，看是否在字符串1里面。很明顯這種的時(shí)間效率為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;
}
思路二
這里由于假定了字符串只包含字母，所以我們可以用一個(gè)額外的數(shù)組flag[26]作為26個(gè)字符標(biāo)識(shí)位，先遍歷長字符串將對(duì)應(yīng)的標(biāo)識(shí)位置1，再遍歷短字符串，如果對(duì)應(yīng)的標(biāo)示位都是1，則包含；否則不包含。這種方法的時(shí)間復(fù)雜度為O(n+m)，為了提高空間效率，這里不使用數(shù)組而使用26個(gè)bit位來作為標(biāo)示位（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;
}
這種方法還可以進(jìn)行優(yōu)化，例如如果長字串的前綴就為短字串，那么我們可以不需要n+m次，而只需要2m次。具體實(shí)現(xiàn)請(qǐng)自己思考。
思路三
給每個(gè)字母分配一個(gè)素?cái)?shù)，從2開始到3，5，7...遍歷長字串，求得每個(gè)字符對(duì)應(yīng)素?cái)?shù)的乘積。然后遍歷短字串，判斷該乘積能否被短字符串中的字符對(duì)應(yīng)的素?cái)?shù)整除，如果除的結(jié)果存在余數(shù)，則說明有不匹配的字母；如果整個(gè)過程都沒有余數(shù)，則說明短字串中的字母在長字串里都有。這種方法的時(shí)間復(fù)雜度也是O(n+m)，需要26個(gè)額外空間存素?cái)?shù)，但是這種方法有一個(gè)缺點(diǎn)就是需要跟大整數(shù)打交道，因?yàn)槌朔e可能非常大。（這里我們使用<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位的有符號(hào)和無符號(hào)整形數(shù) */
/* 在不同位數(shù)機(jī)器的平臺(tái)下通用，都是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;
}
二、比較兩個(gè)字符串是否為變位詞
(1) 問題描述：如果兩個(gè)字符串的字符一樣，但是順序不一樣，被認(rèn)為是兄弟字符串，問如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。
(2) 注意：第一點(diǎn)中討論了字符串包含問題，但是不要以為兩個(gè)字符串互相包含就是（變位詞）兄弟字符串了，例如aabcde和edcba互相包含，但它們不是變位詞。
(3) 解決方案：
思路一
給每個(gè)字母分配一個(gè)素?cái)?shù)，可以通過判斷兩個(gè)字符串的素?cái)?shù)乘積是否相等。跟上述素?cái)?shù)法一樣，時(shí)間復(fù)雜度也是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;
}
思路二
將兩個(gè)字符串按照字母表順序排序，看排序后的字符串是否相等，如果相等則是兄弟字符串（變位詞）。這種方法的時(shí)間效率根據(jù)你使用的排序算法不同而不同。當(dāng)然，你可以自己寫排序算法，這里我們使用C++的STL中的sort()函數(shù)對(duì)字符串進(jìn)行排序。
/*************************************************************************
> 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)
{
// 采用泛型算法對(duì)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;
}
三、字典找出所有變位詞集合（重點(diǎn)）
(1) 問題描述：給定一個(gè)英語字典，找出其中的所有變位詞集合。
(2) 解決方案：
思路一
對(duì)于這個(gè)問題，最快想到的最直接的方法就是針對(duì)每一個(gè)單詞跟字典中的其他單詞進(jìn)行比較。然而，假設(shè)一次比較至少花費(fèi)1微秒的時(shí)間，則擁有二十萬單詞的字典將花費(fèi)：200000單詞 x 200000比較/單詞 x 1微秒/比較 = 40000x10^6秒 = 40000秒 ≈ 11.1小時(shí)。比較的次數(shù)太多了，導(dǎo)致效率低下，我們需要找出效率更高的方法。
思路二
標(biāo)識(shí)字典中的每一個(gè)單詞，使得在相同變位詞類中的單詞具有相同的的標(biāo)識(shí)，然后集中具有相同標(biāo)識(shí)的單詞。將每個(gè)單詞按照字母表排序，排序后得到的字符串作為該單詞的標(biāo)識(shí)。那么對(duì)于該問題的解題過程可以分為三步：第一步，讀入字典文件，對(duì)單詞進(jìn)行排序得到標(biāo)識(shí)；第二步，將所有的單詞按照其標(biāo)識(shí)的順序排序；第三步，將同一個(gè)變位詞類中的各個(gè)單詞放到同一行中。
這里出現(xiàn)了標(biāo)識(shí)-單詞（key-value）對(duì)，我們很容易想到C++中的關(guān)聯(lián)容器map，使用map的好處就是：
動(dòng)態(tài)管理內(nèi)存，容器大小動(dòng)態(tài)改變；
單詞與它的標(biāo)識(shí)一一對(duì)應(yīng)，對(duì)于相同標(biāo)識(shí)(key)的單詞直接加在值(value)后面；
無需根據(jù)標(biāo)識(shí)排序，因?yàn)閙ap會(huì)自動(dòng)按關(guān)鍵字有序（默認(rèn)升序）。
所以，在將每個(gè)單詞及其標(biāo)識(shí)存入map以后，就可以直接遍歷輸出了，每一個(gè)map元素就是一個(gè)變位詞集合。
C++實(shí)現(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++中的關(guān)聯(lián)容器
* 按關(guān)鍵字有序
* 關(guān)鍵字不可重復(fù)
*/
map<string, string> word;
/* 自定義比較函數(shù)（用于排序） */
bool myfunction(char i, char j)
{
return i < j;
}
/*
*對(duì)每個(gè)單詞排序
*排序后字符串作為關(guān)鍵字，原單詞作為值
*存入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);
// 若標(biāo)識(shí)不存在，創(chuàng)建一個(gè)新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百度實(shí)習(xí)筆試題）一個(gè)單詞交換字母位置，可得另一個(gè)單詞，如army->mary，成為兄弟單詞。提供一個(gè)單詞，在字典中找到它的兄弟。描述數(shù)據(jù)結(jié)構(gòu)和查詢過程。
解題思路：如果不允許進(jìn)行預(yù)處理，那么我們只能順序遍歷整個(gè)字典，計(jì)算每個(gè)單詞的標(biāo)識(shí)與給定單詞的標(biāo)識(shí)比較。如果允許進(jìn)行預(yù)處理，我們可以如上述思路二將所有單詞加入一個(gè)map，然后輸出關(guān)鍵字（給定單詞的標(biāo)識(shí)）對(duì)應(yīng)的值，值中就包含了該單詞的所有兄弟單詞。
相信本文所述實(shí)例有助于讀者更好的掌握C++下數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)技巧。
相關(guān)文章
函數(shù)模板實(shí)質(zhì)就是參數(shù)化數(shù)據(jù)類型，稱這種編程模式為數(shù)據(jù)類型泛化編程。本文將通過示例來和大家一起了解下C++中函數(shù)模板的定義與使用，需要的可以參考一下2022-09-09
QT獲取時(shí)間的類有3個(gè)，分別是QDate、QTime、QDateTime,他們屬于QT的network模塊。本文詳細(xì)的介紹了這3個(gè)模塊的使用，感興趣的可以了解一下2023-04-04
C語言數(shù)組學(xué)習(xí)之特殊矩陣的壓縮存儲(chǔ)
矩陣在計(jì)算機(jī)圖形學(xué)、工程計(jì)算中都占有舉足輕重的地位，本文將討論如何將矩陣更有效地存儲(chǔ)在內(nèi)存中，并且能夠方便地提取矩陣中的元素。感興趣的同學(xué)可以了解一下2021-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)單詞小幫手,文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
vector直接翻譯過來為向量,在C++中為封裝動(dòng)態(tài)數(shù)組的容器,且有序,需要的朋友可以參考下2016-05-05
C語言進(jìn)階輸入輸出重定向與fopen函數(shù)使用示例詳解
這篇文章主要為大家介紹了C語言進(jìn)階輸入輸出重定向與fopen函數(shù)的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
通過先序遍歷和中序遍歷后的序列還原二叉樹(實(shí)現(xiàn)方法)
下面小編就為大家?guī)硪黄ㄟ^先序遍歷和中序遍歷后的序列還原二叉樹(實(shí)現(xiàn)方法)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了舉例說明自定義C++異常處理的實(shí)例的相關(guān)資料,這里舉例說明該如何使用C++ 的異常，需要的朋友可以參考下2017-10-10
QT實(shí)戰(zhàn)之打開最近文檔功能的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)打開最近文檔功能，并實(shí)現(xiàn)基本的新建、打開、保存、退出、幫助等功能，感興趣的可以動(dòng)手嘗試一下2022-06-06
Opencv實(shí)現(xiàn)邊緣檢測與輪廓發(fā)現(xiàn)及繪制輪廓方法詳解
這篇文章主要介紹了Opencv實(shí)現(xiàn)邊緣檢測與輪廓發(fā)現(xiàn)及繪制輪廓方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-12-12