连接两个字符串中的不同字符

题意

给出两个字符串, 你需要修改第一个字符串,将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不同字符连接

样例

给出 s1 = aacdb, s2 = gafd
返回 cbgf
给出 s1 = abcs, s2 = cxzca
返回 bsxz

思路

本题我采用了牺牲空间换时间的方式,空间、时间复杂度为 O(m + n)。

以 s1 = aacdb, s2 = gafd 为例

先将 s2 的每一个字符都放进 Map 集合中,将字符当作键,将值赋为 1,此时 Map 集合中应为: {"g':1, "a":1, "f":1, "d": 1}.

然后将 s1 的每一个字符依次判断是否存在与 Map 集合的 Key 中,如果相等则将 集合中该 Key 的值变为 2,如果不相等,则将结果加入到字符串缓冲区中。

进行完这一步操作后,Map 集合中应为:{"g':1, "a":2, "f":1, "d": 2},字符串缓冲区中应为 :cb

最后将 s2 再遍历一次,将在 Map 集合中 Value 为 1 的 Key 依次添加到字符串缓冲区中即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
/*
* @param : the 1st string
* @param : the 2nd string
* @return: uncommon characters of given strings
*/
public String concatenetedString(String s1, String s2) {
StringBuffer sb = new StringBuffer();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : s2.toCharArray()) {
map.put(c, 1);
}

for (char c : s1.toCharArray()) {
if (!map.containsKey(c)) {
sb.append(c);
} else {
map.put(c, 2);
}
}

for (char c : s2.toCharArray()) {
if (map.get(c) != 2) {
sb.append(c);
}
}
return sb.toString();
}
}

原题地址

Lintcode:连接两个字符串中的不同字符