给出两个字符串, 你需要修改第一个字符串,将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不同字符连接
给出 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 依次添加到字符串缓冲区中即可。
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();
}
}