C++變位詞問題分析

來源：本站原創(chuàng)|時間：2020-01-10|欄目：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)管理內存，容器大小動態(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)技巧。

上一篇：C++模板特例化應用實例

欄目：C語言

下一篇：C++可變參數(shù)的函數(shù)與模板實例分析

本文標題：C++變位詞問題分析

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/3498.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

C++變位詞問題分析

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀