算法题

写一个方法：
public String delString(String A,String B){
               .....方法体......
 }
用高效的方式从A中剔除包含B的字符，例如String A="hi are you ok";
String B="io";delString方法返回"h are yu k"
注意：不能使用String的instand of ,splid,char at等等库函数
请问怎么做？我做了,有没什么意见?private String delString( char [] a, char [] b ) {
int max = Integer.MIN_VALUE;
for( char ch : b ) {
if( max  < (int)ch ) {
max = (int)ch;
}
}for( char ch : a ) {
if( max  < (int)ch ) {
max = (int)ch;
}
}int [] arrayA = new int [max + 1];
int [] arrayB = new int [max + 1];
for( char ch : a ) {
arrayA[(int)ch]++;
}
for( char ch : b) {
arrayB[(int)ch]++;
}
for( int i = 0; i  < max; i++ ) {
if( arrayA[i] != 0 && arrayB[i] != 0 ) {
arrayA[i] = 0;
}
}
String s = "";
for( int i = 0; i  < a.length; i++ ) {
if( arrayA[(int)a[i]] != 0 ) s += a[i];
}
return s;
}public void testXixi() {
String A="hi are you ok";
String B="io";
System.out.println( this.delString(A.toCharArray(), B.toCharArray()) );
}算法分析:
这个算法相当浪费空间,但是可以让时间复杂度降到线型
应为如果用迭代得方法,那么时间复杂度是A.length * B.length
但是用这个方法,
我们建立两个int数组,里面储存字母显示字符串A和字符串B的字符的显示的次数
由于两个数组的长度一样,而且对应的index和字符一样,那么只要对比index就可以得出A数组里面有那些字符B里面有,然后把对应的元素的显示次数清零
最后通过数组,把不为零的数组算出来就可以了计算两个数组的长度,算出最大值的时间复杂度是A.length + B.length
计算两个数组里面字符出现的次数的时间复杂度和上面一样
最后清零的时间复杂度是数组的长度(数组最大长度不超过255 because char)
那么最后得出结果的复杂度也 <= A.length
最后我们可以算出 O(n)
这个算法最大的毛病是耗费内存,按时节省了很多的时间.