有一个问题，如何删除两个字符串相同的字符，比如
str1 = "abcdeafg" str2 = "blimklaaaaa"
要得到：
str1 = "cdefg" str2 = "limkl"
下面直接写程序，这个程序是我写的，但是思想是别人的，呵呵
为了方便讨论，假设str1 和 str2 都是ascii码
- void delSameChs(char *str1, char *str2)
- {
- //ascii码是0-255，（准确的说是0-127），所以定义一个临时数组，其下标就是ascii码
- //其元素是出现在下标i出现在str1，str2的次数
- int temp[256];
- char *pStr1 = str1;
- char *pStr2 = str2;
- memset( &temp, 0, sizeof(temp) ); //清0
- while( '/0' != *pStr1 ) //遍历str1，在temp中设为1
- {
- temp[ *pStr1 ] = 1;
- pStr1++;
- }
- while( '/0' != *pStr2 ) //遍历str2, 如果已为1的，在temp中设为2，为2的就是两个字符串的公共元素
- {
- if( 1 == temp[ *pStr2 ] )
- temp[ *pStr2 ] = 2;
- pStr2++;
- }
- for( int i = 0; i < 256; i++ )
- {
- if( 2 == temp[i] )
- {
- delCh(str1, i); //删除str1中所有的字符i（如果有的话）
- delCh(str2, i);
- }
- }
- }
这样做的原理是用空间换时间，牺牲了256个整数的空间（可以用char temp[256]来代替），三遍并列的循环可以把两个数组的相同的元素找出来。如果用常规办法的话，估计要嵌套循环3遍~
如果是unicode嘛，可以设int temp[65536];
如果是多字节编码，这个...我也没想过~
下面看这个 void delChar(char *str, char ch);的实现。
因为要删掉所有的i，如果是常规做法，每删一个元素，后面的就要往前面移动，那就用比较多的时间了。
下面换个做法，看这个代码：
- void delChar( char *str, char ch)
- {
- char *pCurr = str; //用来处理删除后的结果
- char *pTemp = str; //用来扫描源字符串str
- while( '/0' != *pTemp )
- {
- if( ch != *pTemp )
- {
- *pCurr = *pTemp;
- pCurr++;
- }
- pTemp++;
- }
- *pCurr = '/0';
- }
这个代码的思想和常规的不同，移动过去的是不想删掉的，要删的反而不移动它。这样仅需要扫描一次就可以了。
这个样子实现，整个程序最多仅需扫描5次字符串就可以做完任务了。
还可以扩展，如果删除多个字符串的相同字符，都是这样处理，而且复杂度都是O(N)
至于还能不能简化？？？我现在想不出来，各位请多多指教啊，在下感激不尽，呵呵。
注：这个delChar的程序的想法是参考STL algorithm中的unique的源码得到的，特此说明。