The trick here is to name the state correctly, then let the implementation follow. For 819. Most Common Word, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are string_split, mostCommonWord.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- 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
01//Runtime: 12 ms, faster than 17.82% of C++ online submissions for Most Common Word.
02//Memory Usage: 10.4 MB, less than 7.69% of C++ online submissions for Most Common Word.
03
04class Solution {
05public:
06 std::vector<std::string> string_split(std::string str, std::string delimiter){
07 size_t pos = 0;
08 std::string token;
09 std::vector<std::string> result;
10 while ((pos = str.find(delimiter)) != std::string::npos) {
11 token = str.substr(0, pos);
12 result.push_back(token);
13 str.erase(0, pos + delimiter.length());
14 }
15 result.push_back(str);
16 return result;
17 }
18
19 string mostCommonWord(string paragraph, vector<string>& banned) {
20 //replace !?',;. with ' '
21 std::string toRemove = "!?',;.";
22 std::replace_if(paragraph.begin(), paragraph.end(),
23 [toRemove](char c) { return toRemove.find(c) != std::string::npos;}, ' ');
24
25 //remove duplicate spaces
26 paragraph.erase(
27 std::unique(paragraph.begin(), paragraph.end(),
28 [](const char& lhs, const char& rhs){return lhs == ' ' && (lhs == rhs);}
29 ),
30 paragraph.end()
31 );
32
33 transform(paragraph.begin(), paragraph.end(),
34 paragraph.begin(), [](unsigned char c){return tolower(c);});
35 map<string, int> count;
36 string max_word;
37 int max_count = 0;
38
39 for(string word : string_split(paragraph, " ")){
40 if(find(banned.begin(), banned.end(), word) == banned.end()){
41 count[word]++;
42 if(count[word] > max_count){
43 max_word = word;
44 max_count = count[word];
45 }
46 }
47 }
48
49 return max_word;
50 }
51};Cost