I like to read this solution as a small machine: keep the useful information, throw away the noise. For 937. Reorder Data in Log Files, the solution in this repository is mainly a greedy solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: greedy.
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, reorderLogFiles, indices.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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 88.74% of C++ online submissions for Reorder Data in Log Files.
02//Memory Usage: 13.8 MB, less than 47.06% of C++ online submissions for Reorder Data in Log Files.
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 vector<string> reorderLogFiles(vector<string>& logs) {
20 vector<vector<string>> split_logs(logs.size());
21 vector<string> ans(logs.size());
22
23 for(int i = 0; i < logs.size(); i++){
24 split_logs[i] = string_split(logs[i], " ");
25 }
26
27 for(int i = logs.size() - 1, j = logs.size() - 1; i >= 0; i--){
28 //[0]: convert from string to char
29 if(isdigit(split_logs[i][1][0])){
30 ans[j--] = logs[i];
31 logs.erase(logs.begin() + i);
32 split_logs.erase(split_logs.begin() + i);
33 }
34 }
35
36 vector<int> indices(split_logs.size());
37 iota(indices.begin(), indices.end(), 0);
38
39 //move identifier to the end
40 for(int i = 0; i < split_logs.size(); i++){
41 split_logs[i].push_back(split_logs[i][0]);
42 split_logs[i].erase(split_logs[i].begin());
43 }
44
45 sort(indices.begin(), indices.end(),
46 [&split_logs](const int i, const int j){
47 return split_logs[i] < split_logs[j];
48 });
49
50 for(int i = 0; i < indices.size(); i++){
51 ans[i] = logs[indices[i]];
52 }
53
54 return ans;
55 }
56};Cost