Leetcode 884. Uncommon Words from Two Sentences
Problem Explanation:
We are given two sentences. A sentence is defined as a string of space-separated words, where each word is composed only of lowercase letters. Our task is to find and return a list of all uncommon words from the two sentences. A word is defined as uncommon if it appears exactly once in one of the sentences and does not appear in the other sentence. The order of the words in the output list does not matter.
For example, if we have the sentences: A = "this apple is sweet", B = "this apple is sour", then the uncommon words are "sweet" and "sour", since each of these words appears exactly once and only in one of the sentences.
Solution Approach:
The problem can be solved using a frequency counter or an unordered_map in C++. This data structure allows us to keep track of the frequency of each word in both sentences. We separate the words in the sentences by space, and for each word we encounter, we increment its frequency in the counter. At the end, we scan through the counter and add all the words which have a frequency of 1 to our answer list since they are the uncommon words.
Example Walkthrough:
Given the sentences: A = "this apple is sweet", B = "this apple is sour".
-
We can separate each sentence into words. So, for sentence A, we would have the words: "this", "apple", "is", "sweet", and for sentence B, we would have the words: "this", "apple", "is", "sour".
-
Next, we'd increment the frequency of each word in an unordered_map. At this point, the frequency counter would look like: How it would look like:
1 "this": 2 2 "apple": 2 3 "is": 2 4 "sweet": 1 5 "sour": 1
-
Finally, we would add words with a frequency of 1 to our output list, so the output for this example would be ["sweet","sour"] since only these words have a frequency of 1.
C++ Solution:
1
2cpp
3class Solution {
4 public:
5 vector<string> uncommonFromSentences(string A, string B) {
6 vector<string> ans;
7 unordered_map<string, int> count;
8 istringstream iss(A + ' ' + B);
9
10 // Increment the frequency of each word
11 while (iss >> A)
12 ++count[A];
13
14 // Add words with frequency of 1 to the answer list
15 for (const auto& [word, freq] : count)
16 if (freq == 1)
17 ans.push_back(word);
18
19 return ans;
20 }
21};
Java Solution:
1
2java
3class Solution {
4 public String[] uncommonFromSentences(String A, String B) {
5 Map<String, Integer> count = new HashMap();
6 for (String word: (A + " " + B).split(" "))
7 count.put(word, count.getOrDefault(word, 0) + 1);
8 List<String> ans = new LinkedList();
9 for (String word: count.keySet())
10 if (count.get(word) == 1)
11 ans.add(word);
12 return ans.toArray(new String[ans.size()]);
13 }
14}
Python Solution:
1 2python 3class Solution(object): 4 def uncommonFromSentences(self, A, B): 5 count = collections.Counter((A + " " + B).split()) 6 return [word for word in count if count[word] == 1] 7}
JavaScript Solution:
1 2javascript 3var uncommonFromSentences = function(A, B) { 4 let words = (A + ' ' + B).split(' '); 5 let wordCount = {}; 6 for(let word of words){ 7 if(word in wordCount){ 8 wordCount[word] += 1; 9 } else { 10 wordCount[word] = 1; 11 }} 12 return words.filter(word => wordCount[word] === 1); 13};
C# Solution:
1
2csharp
3public class Solution {
4 public string[] UncommonFromSentences(string A, string B) {
5 Dictionary<string, int> count = new Dictionary<string, int>();
6 foreach (string s in (A + " " + B).Split(" ")) {
7 if (count.ContainsKey(s))
8 count[s]++;
9 else
10 count.Add(s, 1);}
11 return count.Where(x => x.Value == 1).Select(x => x.Key).ToArray();}
12};
In all these solutions, we first separate the sentences into words and store their frequencies in a hash map. Then we add the words with a frequency of 1 to our answer list or array. After going through these steps, the list or array should contain all the uncommon words between the two sentences.In conclusion, finding uncommon words between two sentences with the time complexity of O(N), where N is the total number of characters in the strings is quite efficient using the counter approach. We were able to solve the problem by implementing an algorithm in various languages like C++, Python, Java, JavaScript and C#.
This approach can be used in a variety of applications, such as text analysis and natural language processing, where it's often useful to extract unique or unusual words from a body of text. For instance, a variant of this problem might be used to build a rudimentary spell-checker. A more in-depth application might be analyzing transcripts of speech to determine what words or phrasing are unique to certain speakers.
These solutions effectively demonstrate the application of frequency counter data structure to solve the problem. While the method of implementation differed slightly with each language, the underlying logic remained the same. This example serves as a strong reminder of how an understanding of key data structures and algorithms can be applied across multiple programming languages to solve the same problem. Moreover, hash maps are a key element in solving problems involving frequency counting, making them an important tool for data handling and manipulation in programming.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.