937. Reorder Log Files

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: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

1. 0 <= logs.length <= 100

2. 3 <= logs[i].length <= 100

3. logs[i] is guaranteed to have an identifier, and a word after the identifier.

vector<string> reorderLogFiles(vector<string>& logs) {
    vector<string> digit_container, res;
    map<string, set<string> > mp; // without identifier -> with identifier
    for (string& log : logs) {
        int pos = log.find(' ');
        string str = log.substr(pos + 1);
        if (str[0] >= '0' && str[0] <= '9') {
            digit_container.push_back(log);
        } else {
            mp[str].insert(log);
        }
    }
    for (auto mit = mp.begin(); mit != mp.end(); ++mit) {
        for (auto sit = mit->second.begin(); sit != mit->second.end(); ++sit) {
            res.push_back(*sit);
        }
    }
    for (const string& digit_str : digit_container) {
        res.push_back(digit_str);
    }
    return res;
}

寫一個self-defined comparator。

// std stable sort with self-defined comparator
static bool myComp(const string& a, const string& b) {
    int i = a.find(' '), j = b.find(' ');
    if (isdigit(a[i + 1])) {
        if (isdigit(b[j + 1])) 
            return false; // a & b are digits, keep the original orders
        else 
            return false; // a is digit, b is letter, b < a
    } else {
        if (isdigit(b[j + 1]))
            return true; // a is letter, b is digit, a < b
        else {
            if (a.substr(i) == b.substr(j)) 
                return a.substr(0, i) < b.substr(0, j); // a w/o identifer == b w/o identifier, compare identifier
            else
                return a.substr(i) < b.substr(j); // a & b are letter logs, compare the letter logs
        }
    }
}
vector<string> reorderLogFiles(vector<string>& logs) { // time: O(nlogn); space: O(n)
    vector<string> res(logs.begin(), logs.end());
    stable_sort(logs.begin(), logs.end(), myComp);
    return logs;
}