在字符串中删除特定的字符

题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。

首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符,需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话,对于一个长度为n的字符串而言,删除一个字符的时间复杂度为O(n)。而对于本题而言,有可能要删除的字符的个数是n,因此该方法就删除而言的时间复杂度为O(n2)。

事实上,我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想,当一个字符需要被删除的时候,我们把它所占的位置让它后面的字符来填补,也就相当于这个字符被删除了。在具体实现中,我们可以定义两个指针(pFast和pSlow),初始的时候都指向第一字符的起始位置。当pFast指向的字符是需要删除的字符,则pFast直接跳过,指向下一个字符。如果pFast指向的字符是不需要删除的字符,那么把pFast指向的字符赋值给pSlow指向的字符,并且pFast和pStart同时向后移动指向下一个字符。这样,前面被pFast跳过的字符相当于被删除了。用这种方法,整个删除在O(n)时间内就可以完成。

接下来我们考虑如何在一个字符串中查找一个字符。当然,最简单的办法就是从头到尾扫描整个字符串。显然,这种方法需要一个循环,对于一个长度为n的字符串,时间复杂度是O(n)。

由于字符的总数是有限的。对于八位的char型字符而言,总共只有28=256个字符。我们可以新建一个大小为256的数组,把所有元素都初始化为0。然后对于字符串中每一个字符,把它的ASCII码映射成索引,把数组中该索引对应的元素设为1。这个时候,要查找一个字符就变得很快了:根据这个字符的ASCII码,在数组中对应的下标找到该元素,如果为0,表示字符串中没有该字符,否则字符串中包含该字符。此时,查找一个字符的时间复杂度是O(1)。其实,这个数组就是一个hash表。这种思路的详细说明,详见第一个只出现一次的字符

基于上述分析,我们可以写出如下代码:

///////////////////////////////////////////////////////////////////////
// Delete all characters in pStrDelete from pStrSource
///////////////////////////////////////////////////////////////////////
void DeleteChars(char* pStrSource, const char* pStrDelete)
{
      if(NULL == pStrSource || NULL == pStrDelete)
            return;

      // Initialize an array, the index in this array is ASCII value.
      // All entries in the array, whose index is ASCII value of a
      // character in the pStrDelete, will be set as 1.
      // Otherwise, they will be set as 0.
      const unsigned int nTableSize = 256;
      int hashTable[nTableSize];
      memset(hashTable, 0, sizeof(hashTable));

      const char* pTemp = pStrDelete;
      while ('\0' != *pTemp)
      {
            hashTable[*pTemp] = 1;
            ++ pTemp;
      }

      char* pSlow = pStrSource;
      char* pFast = pStrSource;
      while ('\0' != *pFast)
      {
            // if the character is in pStrDelete, move both pStart and
            // pEnd forward, and copy pEnd to pStart.
            // Otherwise, move only pEnd forward, and the character
            // pointed by pEnd is deleted
            if(1 != hashTable[*pFast])
            {
                  *pSlow = *pFast;
                  ++ pSlow;
            }

            ++pFast;
      }

      *pSlow = '\0';
}

 memset函数使用方法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

正则表达式(四):Java regex

Java 作为一种被广泛使用的编程语言,从 jdk-1.4 开始,标准库提供了 java.util.regex 包来支持正则表达式的使用。正则在 Java 中的...

28620
来自专栏锦小年的博客

python学习笔记2.4-数据结构之列表和元组

python语言中包含的数据结构比较简单,除了简单的变量以外,还有列表(元组)、字典、集合。对于数据结构的操作一般包含四种:增、删、查、改。本文主要介绍列表(l...

19990
来自专栏一个会写诗的程序员的博客

JS中的phototypeJS中的phototype

原型法的主要思想是,现在有1个类A,我想要创建一个类B,这个类是以A为原型的,并且能进行扩展。我们称B的原型为A。

10110
来自专栏好好学java的技术栈

Java基础提升篇:equals()方法和“==”运算符

10230
来自专栏C语言及其他语言

结构体与共用体

1、结构体的定义和使用 前面我们已经讨论过字符数组与字符串,字符指针也可以指向一个字符串,可以用字符串常量对字符 指针进行初始化。例如: char *str...

33970
来自专栏calmound

Javascript字符串

## 定义 ``` var str = new String("abcdefg"); var str = "abcdefg"; ``` ## 常用方法 ###...

30160
来自专栏刘晓杰

正则表达式

27890
来自专栏积累沉淀

Python快速学习第六天

第六天: 面向对象 1. 面向对象的特点——多态,封装,继承  对象:包括特性和方法,特性只是作为对象的一部分变量,而方法则是存储在对象内的函数。 (1)多态—...

19570
来自专栏赵俊的Java专栏

删除排序数组中的重复数字

14020
来自专栏移动端开发

swift 运算符快速学习(建议懂OC或者C语言的伙伴学习参考)

  昨晚看了swift 的运算符的知识点,先大概说一下,这个点和 c 或者oc 的算运符知识点一样,都是最基础最基础的。其他的最基本的加减乘除就不多说了。注意的...

22280

扫码关注云+社区

领取腾讯云代金券