1.问题描述
Example 1:
Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"] Example 2:
Input: A = "apple apple", B = "banana"
Output: ["banana"]
要求：
- 某个单词在它自己所在的句子中仅出现一次。
- 某个单词在另外一个句子中没有出现过。
- 将两个句子中同时满足上述两个要求的单词输出到列表中。
2.我自己的解题思路
- 将两个字符串转换成List并且按照默认的排序规则排序，例如，将"uuz rk uuz"排序成"rk uuz uuz"，这是为了在后面将在同一个句子中出现两次即以上的单词排除。
- 使用一个中间字符串tmp当做指针来按照List里面的顺序依次指向每个元素，由于有了前面的已经排好顺序的代码，所以这里采用的方法是，如果List中有某个单词出现了两次或两次以上，例如"rk uuz uuz"，先将uuz加入到list中，然后比较第一个uuz和第二个uuz相同，将之前加入list的uuz移除。（由于对HashMap不太熟悉，使用这种方法也可以通过，但是会比较麻烦，复杂度也较高。）
- 在满足上面的判断条件后，判断某个单词是否在另外一个句子中出现过，如果没有出现过，就加入到结果集list中。
public String[] uncommonFromSentences(String A, String B) {
List<String> list = new LinkedList<>();
String[] aStr = A.split(" ");
String[] bStr = B.split(" ");
List<String> aList = Arrays.asList(aStr);
List<String> bList = Arrays.asList(bStr);
Collections.sort(aList);
Collections.sort(bList);
String tmp1 = "";
for (Iterator<String> iterator = aList.iterator(); iterator.hasNext();) {
String string = (String) iterator.next();
if (!tmp1.equals(string)) {
if (!bList.contains(string)) {
list.add(string);
tmp1 = string;
}
} else {
list.remove(tmp1);
}
}
String tmp2 = "";
for (Iterator<String> iterator = bList.iterator(); iterator.hasNext();) {
String string = (String) iterator.next();
if (!tmp2.equals(string)) {
if (!aList.contains(string)) {
list.add(string);
tmp2 = string;
}
} else {
list.remove(tmp2);
}
}
String[] result = new String[list.size()];
list.toArray(result);
return result;
}3.应该要用的解题思路：HashMap
使用HashMap集合将A和B两个句子中的所有单词作为键key，将每个单词对应的出现次数作为值value。
count.getOrDefault(word, 0)的意思是，如果集合中已经存在word这个键，就使用其对应的value值，否则，使用默认的值0，用来判断单词出现的次数。
然后统计HashMap集合中每个单词对应的值value，如果等于1就说明只出现了一次，然后加入到结果集ans中即可。
时间复杂度：O(M+N)，M是A的复杂度，N是B的复杂度。
空间复杂度：O(M+N)，使用的HashMap集合count所占用的空间。
class Solution {
public String[] uncommonFromSentences(String A, String B) {
Map<String, Integer> count = new HashMap();
for (String word: A.split(" "))
count.put(word, count.getOrDefault(word, 0) + 1);
for (String word: B.split(" "))
count.put(word, count.getOrDefault(word, 0) + 1);
List<String> ans = new LinkedList();
for (String word: count.keySet())
if (count.get(word) == 1)
ans.add(word);
return ans.toArray(new String[ans.size()]);
}
}