首页 > 代码库 > 字符串删除问题
字符串删除问题
在计算机的世界里,字符串问题可以说是一个很重要的问题,比如文本处理等等问题。今天Mayuyu就来讲述一个字符串删除问题,问题描述如下
问题:给定一个很长的字符串,比如长度为1000000,现在要删除这个字符串中某些指定的字符,这些指定的字符只
有几个,现在Mayuyu要求是尽量用最少的时间和空间来做这件事。
分析:很明显,可以从前往后扫描,遇到一个指定的字符就删除,然后把后面的往前移动。很显然,这样做时间复杂度
太大啊,所以很有必要设计一个比较好的算法。其实可以这样考虑,我们可以用两个指针从前往后扫描,遇到需
要删除的就将后面的字符串拿来覆盖之前的,这样下去时间复杂度是O(n)的,而且不需要开额外空间。至于怎
么找指定的字符是否存在,只需要先用一个数组预处理即可。
代码:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; int flag[123]; //大写字母和小写字母的ASCII值最多到122 void Init(const char *str) { memset(flag, 0, sizeof(flag)); while(*str) flag[*str++] = 1; } void Delete(char *str) { char *pFast = str; char *pSlow = str; while(*pFast) { if(!flag[*pFast]) *pSlow++ = *pFast++; else pFast++; } *pSlow = 0; } int main() { char source[] = "Hello Mayuyu!!!"; char word[] = "Hello"; Init(word); Delete(source); cout << source << endl; return 0; }
字符串删除问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。