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;
}

思路二

这里由于假定了字符串只包含字母,所以我们可以用一个额外的数组flag[26]作为26个字符标识位,先遍历长字符串将对应的标识位置1,再遍历短字符串,如果对应的标示位都是1,则包含;否则不包含。这种方法的时间复杂度为O(n+m),为了提高空间效率,这里不使用数组而使用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;
}

这种方法还可以进行优化,例如如果长字串的前缀就为短字串,那么我们可以不需要n+m次,而只需要2m次。具体实现请自己思考。

思路三

给每个字母分配一个素数,从2开始到3,5,7...遍历长字串,求得每个字符对应素数的乘积。然后遍历短字串,判断该乘积能否被短字符串中的字符对应的素数整除,如果除的结果存在余数,则说明有不匹配的字母;如果整个过程都没有余数,则说明短字串中的字母在长字串里都有。这种方法的时间复杂度也是O(n+m),需要26个额外空间存素数,但是这种方法有一个缺点就是需要跟大整数打交道,因为乘积可能非常大。(这里我们使用<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位的有符号和无符号整形数 */
  /* 在不同位数机器的平台下通用,都是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) 解决方案:

思路一

给每个字母分配一个素数,可以通过判断两个字符串的素数乘积是否相等。跟上述素数法一样,时间复杂度也是O(n+m),需要跟大整数打交道。

/*************************************************************************
  > 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;
}

思路二

将两个字符串按照字母表顺序排序,看排序后的字符串是否相等,如果相等则是兄弟字符串(变位词)。这种方法的时间效率根据你使用的排序算法不同而不同。当然,你可以自己写排序算法,这里我们使用C++的STL中的sort()函数对字符串进行排序。

/*************************************************************************
  > File Name: test4.cpp
  > Author: SongLee
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<string>
using namespace std; 

// 自定义序函数(二元谓词)
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小时。比较的次数太多了,导致效率低下,我们需要找出效率更高的方法。

思路二

标识字典中的每一个单词,使得在相同变位词类中的单词具有相同的的标识,然后集中具有相同标识的单词。将每个单词按照字母表排序,排序后得到的字符串作为该单词的标识。那么对于该问题的解题过程可以分为三步:第一步,读入字典文件,对单词进行排序得到标识;第二步,将所有的单词按照其标识的顺序排序;第三步,将同一个变位词类中的各个单词放到同一行中。

这里出现了标识-单词(key-value)对,我们很容易想到C++中的关联容器map,使用map的好处就是:

动态管理内存,容器大小动态改变;
单词与它的标识一一对应,对于相同标识(key)的单词直接加在值(value)后面;
无需根据标识排序,因为map会自动按关键字有序(默认升序)。
所以,在将每个单词及其标识存入map以后,就可以直接遍历输出了,每一个map元素就是一个变位词集合。

C++实现代码如下:

/*************************************************************************
  > 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++中的关联容器
 *   按关键字有序
 *   关键字不可重复
 */
map<string, string> word; 

/* 自定义比较函数(用于排序) */
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);
    // 若标识不存在,创建一个新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,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。

解题思路:如果不允许进行预处理,那么我们只能顺序遍历整个字典,计算每个单词的标识与给定单词的标识比较。如果允许进行预处理,我们可以如上述思路二将所有单词加入一个map,然后输出关键字(给定单词的标识)对应的值,值中就包含了该单词的所有兄弟单词。

相信本文所述实例有助于读者更好的掌握C++下数据结构与算法的实现技巧。

(0)

相关推荐

  • C++快速排序的分析与优化详解

    相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值.具体分析如下: 一.快速排序的介绍 快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta].虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择.这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小.另外,它还能够进行就地排序,在虚拟内存

  • C++实现矩阵原地转置算法

    本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析 下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到

  • C++中虚函数与纯虚函数的用法

    本文较为深入的分析了C++中虚函数与纯虚函数的用法,对于学习和掌握面向对象程序设计来说是至关重要的.具体内容如下: 首先,面向对象程序设计(object-oriented programming)的核心思想是数据抽象.继承.动态绑定.通过数据抽象,可以使类的接口与实现分离,使用继承,可以更容易地定义与其他类相似但不完全相同的新类,使用动态绑定,可以在一定程度上忽略相似类的区别,而以统一的方式使用它们的对象. 虚函数的作用是实现多态性(Polymorphism),多态性是将接口与实现进行分离,采用

  • C++深度优先搜索的实现方法

    本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.深度优先搜索(DFS)的算法思想 深度优先搜索算法所遵循的搜索策略是尽可能"深&

  • C++实现第K顺序统计量的求解方法

    一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们这里要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量.该问题的算法对于C++程序员来说有一定的借鉴价值.具体如下: 一.问题描述: 问题:给定一个含有n个元素的无序数组,找出第k小的元素. k = 1 :最小值 k = n :最大值 k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ :中位数 找最大值或最小值很简单,只需要遍历一次数组并记录下最大值或最

  • C++中extern "C"的用法

    学习过C++的人都知道,extern关键字可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义.这里起到的是声明作用范围的用处.另外,extern还可以与"C"连用,作为链接指示.本文就此进行实例说明如下: 一.C++名字修饰(Name Mangling) 首先需要从C++的重载说起,在C++中函数重载指的是几个函数的函数名相同,参数列表不同.那么当生成obj中间文件/目标文件的时候,C++编译器如何区分这几个重载函数呢?可以

  • C++与C的差异分析

    虽说C++是向后兼容C的,但C++与C还是存在许多差异.本文列举了几个例子加以说明,同时这些也是我们非常容易忽略的地方.本文仅简单的列举几例,更多的不同之处读者还需要在学习与实践中不断的进行发掘和总结. C编译通过但C++编译不通过: 1.C++中编译器不允许在一个函数声明之前调用它,但C中编译器是允许的. #include<stdio.h> // 请用gcc和g++分别进行编译 int main() { foo(); // foo()在它的声明/定义之前被调用 } int foo() { p

  • C++继承中的访问控制实例分析

    本文较为深入的探讨了C++继承中的访问控制,对深入掌握C++面向对象程序设计是非常必要的.具体内容如下: 通常来说,我们认为一个类有两种不同的用户:普通用户 和 类的实现者.其中,普通用户编写的代码使用类的对象,这部分代码只能访问类的公有(接口)成员:实现者则负责编写类的成员和友元的代码,成员和友元既能访问类的公有部分,也能访问类的私有部分.如果进一步考虑继承的话就会出现第三种用户,即派生类.派生类可以访问基类的公有(public)成员和受保护(protected)成员,但不能访问基类的私有(p

  • C++实现广度优先搜索实例

    本文主要叙述了图的遍历算法中的广度优先搜索(Breadth-First-Search)算法,是非常经典的算法,可供C++程序员参考借鉴之用.具体如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.广度优先搜索(BFS)的

  • C++线性时间的排序算法分析

    前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线性时间运行. 一.比较排序算法的时间下界 所谓的比较排序是指通过比较来决定元素间的相对次序. "定理:对于含n个元素的一个输入序列,

随机推荐