How to Uncommon Words from Two Sentences in Java?

  • 时间：2020-10-05 13:36:40
  • 分类：网络文摘
  • 阅读：141 次

We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

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”]

The first intuitive solution is to split both strings by spaces (into words array) and record their count in two separate HashMaps.

Then, the next step is to iterative over both string arrays (words) and to check if words appear in once sentences and not in another.

The following Java implementation to get the uncommon words from two sentences is quite verbose.

The time and space complexity is O(M + N) where M and N are the length of both strings (sentences)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public String[] uncommonFromSentences(String A, String B) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> a = new HashMap<>();
        Map<String, Integer> b = new HashMap<>();
        String[] wordsA = A.split(" ");
        String[] wordsB = B.split(" ");
        for (String x: wordsA) {
            if (a.containsKey(x)) {
                a.put(x, a.get(x) + 1);
            } else {
                a.put(x, 1);
            }
        }
        for (String x: wordsB) {
            if (b.containsKey(x)) {
                b.put(x, b.get(x) + 1);
            } else {
                b.put(x, 1);
            }
        }
        for (String x: wordsA) {
            if (a.containsKey(x)) {
                if ((a.get(x) == 1) && (!b.containsKey(x))) {
                    result.add(x);
                }
            } else {
                if (b.containsKey(x) && (b.get(x) == 1)) {
                    result.add(x);
                }
            }
        }
        for (String x: wordsB) {
            if (a.containsKey(x)) {
                if ((a.get(x) == 1) && (!b.containsKey(x))) {
                    result.add(x);
                }
            } else {
                if (b.containsKey(x) && (b.get(x) == 1)) {
                    result.add(x);
                }
            }
        }    
        return result.toArray(new String[0]);
    }
}
class Solution {
    public String[] uncommonFromSentences(String A, String B) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> a = new HashMap<>();
        Map<String, Integer> b = new HashMap<>();
        String[] wordsA = A.split(" ");
        String[] wordsB = B.split(" ");
        for (String x: wordsA) {
            if (a.containsKey(x)) {
                a.put(x, a.get(x) + 1);
            } else {
                a.put(x, 1);
            }
        }
        for (String x: wordsB) {
            if (b.containsKey(x)) {
                b.put(x, b.get(x) + 1);
            } else {
                b.put(x, 1);
            }
        }
        for (String x: wordsA) {
            if (a.containsKey(x)) {
                if ((a.get(x) == 1) && (!b.containsKey(x))) {
                    result.add(x);
                }
            } else {
                if (b.containsKey(x) && (b.get(x) == 1)) {
                    result.add(x);
                }
            }
        }
        for (String x: wordsB) {
            if (a.containsKey(x)) {
                if ((a.get(x) == 1) && (!b.containsKey(x))) {
                    result.add(x);
                }
            } else {
                if (b.containsKey(x) && (b.get(x) == 1)) {
                    result.add(x);
                }
            }
        }    
        return result.toArray(new String[0]);
    }
}

In java, we can convert the List of String into an array of String by using list.toArray(new String[0]) or list.toArray(new String[list.size()])

Also, as we are counting, we can get rid of hashMap.containsKey() check by using hashMap.getOrDefault which takes two parameter, the key and the default value if it is not set in the hash map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public String[] uncommonFromSentences(String A, String B) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> a = new HashMap<>();
        for (String x: A.split(" ")) {
            a.put(x, a.getOrDefault(x, 0) + 1);
        }
        for (String x: B.split(" ")) {
            a.put(x, a.getOrDefault(x, 0) + 1);
        }
        for (String x: a.keySet()) {
            if (a.get(x) == 1) {
                result.add(x);
            }
        }
        return result.toArray(new String[0]);
    }
}
class Solution {
    public String[] uncommonFromSentences(String A, String B) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> a = new HashMap<>();
        for (String x: A.split(" ")) {
            a.put(x, a.getOrDefault(x, 0) + 1);
        }
        for (String x: B.split(" ")) {
            a.put(x, a.getOrDefault(x, 0) + 1);
        }
        for (String x: a.keySet()) {
            if (a.get(x) == 1) {
                result.add(x);
            }
        }
        return result.toArray(new String[0]);
    }
}

And we don’t need two separate hash maps, just use one and count the frequencies of words from both sentences. Later, if the counter is only one from any words, we know it is a uncommon words, thus adding it to the final array.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
CCTV13在线直播-中央十三台直播在线观看「高清」　 CCTV14在线直播-中央十四台直播在线观看「高清」　 CCTV15在线直播-中央十五台直播在线观看「高清」　 CETV1在线直播-中国教育电视台一套直播「高清」　 CETV2在线直播-中国教育电视台二套直播「高清」　 CETV3在线直播-中国教育电视台三套直播「高清」　 CETV4在线直播-中国教育电视台四套直播「高清」　 中国气象频道在线直播「高清」　 中国之声在线收听「听广播」　 经济之声在线收听「听广播」　
评论列表
添加评论