首页 > 代码库 > 待字闺中之删除字符分析

待字闺中之删除字符分析

删除字符串中的“b”和“ac”,需要满足如下的条件:

1. 字符串只能遍历一次

2. 不能够使用额外的空间

例如:

1. acbac   ==>  ""

2. aaac    ==>  aa

3. ababac  ==>  aa

4. bbbbd   ==>  d

进一步思考:如何处理aaccac呢,需要做哪些改变呢?

分析

首先要明白从字符串中删除某些字符该如何实现,显而易见我们可以把保留的字符拷贝新的字符串中来实现删除。但是题目要求不能使用额外的空间。那就是将要删除的字符全部交换到字符串的尾部,然后设置一个‘\0‘表示字符串的结尾。

其次,如果要删除的都是单个字符的字符串,就很直接:我们使用i和j两个变量遍历字符串,i表示不会删除的字符的位置,j从0开始,只要i所在位置 的字符不是要删除的字符,就str[j]=str[i](str表示字符串),然后j++指向下一个位置。一次遍历即可,不需要额外申请空间,只需要两个 变量。

但是,现在删除的字符串中有多个字符的,如:“ac”。那要如何处理呢?这里介绍一个小技巧:状态机。这里,我们有两个状态:ONE和TWO。TWO表示,前一个字符时‘a’的状态,其他的都用ONE表示。还是采用前面所描述的遍历方法:

1. 如果当前状态为ONE,则拷贝:str[j]=str[i];但如果当前字符满足以下两种状态的任一个,则不进行拷贝:

    1. 当前字符是‘b’,因为我们要删除b

    2. 当前字符是‘a’,我们要考虑下一个字符是c


2. 如果当前状态为TWO

    1. 当前字符不是‘c’,那么我们要先拷贝前一个字符‘a

    2. 然后考虑当前字符,如果不是‘b’或者‘a’,则拷贝字符

状态转换非常简单,就是每次都检查,是前一个字符为‘a’。基本代码如下:

void stringFilter(char* str)
{
	int i,j=0,length = strlen(str),STATE = 1;
	for (i = 0;i < length;i++)
	{
		//状态为ONE的情况
		if (STATE == 1 && str[i] != 'a' && str[i] != 'b')
		{
			str[j++] = str[i];
		}
		//状态为TWO的情况
		else if (STATE == 2 && str[i] != 'c')
		{
			str[j++] = 'a';
			if (str[i] != 'a' && str[i] != 'b')
			{
				str[j++] = str[i];
			}
		}
		//跟新当前状态
		STATE = str[i] == 'a' ? 2 : 1;
		
		//如果需要删除不连续的ac,则打开
		//if (j > 1 && str[j-2] == 'a' && str[j-1] == 'c') j -= 2;
	}
	if(STATE == 2)str[j++] = 'a';
	str[j] = '\0';
}

下面进一步考虑: 根据上面的算法,我们考虑aaccac,最终得到ac。ac在题目中要求的也是要删除的。是否要删除这个ac,就需要和面试官进行交流了,无论如何,总是 要考虑这种情况。还是采用上面的算法,怎么解决删除之后还可以删除的情况?只要把循环最后的代码注释去调即可

待字闺中之删除字符分析