How to Reorder Data in Log Files using the Custom Sorting Algorithm?

You have an array of logs. Each log is a space delimited string of words.
For each log, the first word in each log is an alphanumeric identifier.

Then, either:
Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.
Example 1:
Input: logs = [“dig1 8 1 5 1″,”let1 art can”,”dig2 3 6″,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1″,”dig2 3 6″]

Constraints:
0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Custom Sorting Procedure

The C++ sort() and stable_sort() can use the custom sorting procedure which you can pass a lambda, or a customize function that returns true or false which determines the order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(begin(logs), end(logs), [](auto &a, auto &b) {
            bool aa = isalpha(a.back());
            bool bb = isalpha(b.back());
            if (aa && bb) {
                int i = a.find(' ');
                int j = b.find(' ');
                string w1 = a.substr(i + 1);
                string w2 = b.substr(j + 1);
                string i1 = a.substr(0, i);
                string i2 = b.substr(0, j);
                return w1 == w2 ? i1 <= i2 : w1 < w2;
            }
            if (aa && (!bb)) {
                return true;                
            }
            return false;
        });
        return logs;
    }
};

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(begin(logs), end(logs), [](auto &a, auto &b) {
            bool aa = isalpha(a.back());
            bool bb = isalpha(b.back());
            if (aa && bb) {
                int i = a.find(' ');
                int j = b.find(' ');
                string w1 = a.substr(i + 1);
                string w2 = b.substr(j + 1);
                string i1 = a.substr(0, i);
                string i2 = b.substr(0, j);
                return w1 == w2 ? i1 <= i2 : w1 < w2;
            }
            if (aa && (!bb)) {
                return true;                
            }
            return false;
        });
        return logs;
    }
};

Given the size of the input may be large, we need to use stable_sort over unstable sort, as required that we need to put the digital logs in the original order.

We can check the last character of the log to determine if they are letter-logs if the last character isalpha(). Then we use the string.find to find the index of the first appeared space, which then we can use the string.substr to separate the identifier and the rest.

–EOF (The Ultimate Computing & Technology Blog) —