A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 884. Uncommon Words from Two Sentences, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are string_split, uncommonFromSentences, insert_or_increment.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)
03A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.
04Return a list of all uncommon words.
05You may return the list in any order.
06
07Example 1:
08
09Input: A = "this apple is sweet", B = "this apple is sour"
10Output: ["sweet","sour"]
11Example 2:
12
13Input: A = "apple apple", B = "banana"
14Output: ["banana"]
15**/
16
17//Runtime: 8 ms, faster than 66.46% of C++ online submissions for Uncommon Words from Two Sentences.
18//Memory Usage: 11.4 MB, less than 5.55% of C++ online submissions for Uncommon Words from Two Sentences.
19class Solution {
20public:
21 vector<string> string_split(string str){
22 size_t pos = 0;
23 string token;
24 string delimiter = " ";
25 vector<string> str_vec;
26
27 while ((pos = str.find(delimiter)) != string::npos) {
28 token = str.substr(0, pos);
29 str_vec.push_back(token);
30 str.erase(0, pos + delimiter.length());
31 }
32
33 //add the last token
34 str_vec.push_back(str);
35
36 return str_vec;
37 }
38
39 vector<set<string>> removeDuplicates(vector<string>& v){
40 set<string> dup;
41
42 for(string s : v){
43 if(count(v.begin(), v.end(), s) > 1){
44 dup.insert(s);
45 //cannot erase element while iterating it
46 // v.erase(remove(v.begin(), v.end(), s), v.end());
47 }
48 }
49 for(string s : dup){
50 v.erase(remove(v.begin(), v.end(), s), v.end());
51 }
52 return vector<set<string>> {set<string> (v.begin(), v.end()), dup};
53 }
54
55 vector<string> uncommonFromSentences(string A, string B) {
56 vector<string> vA = string_split(A);
57 vector<string> vB = string_split(B);
58
59 //remove duplicate elements
60 vector<set<string>> udA = removeDuplicates(vA);
61 vector<set<string>> udB = removeDuplicates(vB);
62
63 set<string> uA = udA[0];
64 set<string> uB = udB[0];
65 set<string> dA = udA[1];
66 set<string> dB = udB[1];
67
68 //symmetric difference
69 //allocate vector size as sA.size()+sB.size(),
70 // because if sA and sB are all different,
71 // it will need that amount of space
72 set<string> uncommons;
73 set<string>::iterator s_it;
74
75 // the xor of two sets
76 set_symmetric_difference(uA.begin(), uA.end(),
77 uB.begin(), uB.end(),
78 inserter(uncommons, uncommons.begin()));
79
80 // remove duplicate from dA
81 set<string> tmp;
82 set_difference(make_move_iterator(uncommons.begin()),
83 make_move_iterator(uncommons.end()),
84 dA.begin(), dA.end(),
85 inserter(tmp, tmp.begin()));
86 uncommons.swap(tmp);
87 tmp.clear();
88
89 // remove duplicate from dB
90 set_difference(make_move_iterator(uncommons.begin()),
91 make_move_iterator(uncommons.end()),
92 dB.begin(), dB.end(),
93 inserter(tmp, tmp.begin()));
94 uncommons.swap(tmp);
95 tmp.clear();
96
97 return vector<string> (uncommons.begin(), uncommons.end());
98 }
99};
100
101/**
102Approach 1: Counting
103Intuition and Algorithm
104
105Every uncommon word occurs exactly once in total.
106We can count the number of occurrences of every word,
107then return ones that occur exactly once.
108**/
109/**
110Complexity Analysis
111Time Complexity: O(M+N), where M, N are the lengths of A and B respectively.
112Space Complexity: O(M+N), the space used by count.
113**/
114//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Uncommon Words from Two Sentences.
115//Memory Usage: 9.6 MB, less than 11.11% of C++ online submissions for Uncommon Words from Two Sentences.
116class Solution {
117public:
118 vector<string> string_split(string str){
119 size_t pos = 0;
120 string token;
121 string delimiter = " ";
122 vector<string> str_vec;
123
124 while ((pos = str.find(delimiter)) != string::npos) {
125 token = str.substr(0, pos);
126 str_vec.push_back(token);
127 str.erase(0, pos + delimiter.length());
128 }
129
130 //add the last token
131 str_vec.push_back(str);
132
133 return str_vec;
134 }
135
136 template <class K, class V>
137 void insert_or_increment(map<K,V>& mymap, K key, V inc){
138 if(mymap.find(key)==mymap.end()){
139 mymap[key] = 0+inc;
140 }else{
141 mymap[key] += inc;
142 }
143 }
144
145 vector<string> uncommonFromSentences(string A, string B) {
146 vector<string> vA = string_split(A);
147 vector<string> vB = string_split(B);
148 map<string, int> mymap;
149 vector<string> ans;
150
151 for(string e : vA){
152 insert_or_increment(mymap, e, 1);
153 }
154
155 for(string e : vB){
156 insert_or_increment(mymap, e, 1);
157 }
158
159 for(pair<string, int> p : mymap){
160 if(p.second==1){
161 ans.push_back(p.first);
162 }
163 }
164
165 return ans;
166 }
167};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.