学步园

微软笔试100题中的题目。

给定一个源字符串和一个要删除的字符数组，删除源字符串中的特定字符。

用hashmap来加速查询，用快慢下标做数组元素移位，将不需要删除的元素向前移动。

代码如下：

package static_;

import java.util.HashMap;

public class CopyOfTest {

	public static void main(String[] args) throws Exception {
		System.out.println(get("aaaaaeeeiioouuuaaakkkdddaakkakakakkabcdefghijk", "aeiou"));
	}

	// 删除s1中的包含在s2中的字符
	public static String get(String s1, String s2) {
		char[] cs = s1.toCharArray();
		HashMap<String, String> map = new HashMap<String, String>();
		for (int i = 0; i < s2.length(); i++) {
			map.put(s2.charAt(i) + "", "");
		}
		int p1 = 0;
		int p2 = 0;
		for (int i = 0; i < cs.length; i++) {
			String cur = cs[i] + "";
			String res = map.get(cur);
			if (res != null) {
				// 这个字符要删除
				p2++;
			} else {
				// 这个字符不删除
				cs[p1] = cs[i];// 不删除的字符移动到p1位置
				p1++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < p1; i++) {
			sb.append(cs[i]);
		}
		return sb.toString();
	}
}

整体时间复杂度为o(n)。空间复杂度就是将要删除的字符占用的空间。如果想让空间复杂度为0，可以将s2排序，然后用二分查找加速查询。