Question

Formatted question description: https://leetcode.ca/all/937.html

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.

Algorithm

In fact, this question is a more complicated sorting problem. The two types of logs need to be processed separately. For digital logs, sorting is not required, but the original order must be recorded. Here you can use an array to save the digital log, so that it is added after the result res, and its original order can be maintained.

The key is to sort the alphabetic logs and extract the identifiers, so that when traversing the logs, find the position of the first space first, so that the first part is the identifier, and the following content is the log content , The character immediately following the space is judged at this time. If it is a number, it means that the current log is of digital type. Add it to the array digitLogs and continue to loop. If not, separate the two parts and store them in a two-dimensional array data. After that, the data array needs to be sorted, and the sorting rules need to be rewritten. It is sorted according to the log content. If the log content is equal, it is sorted according to the identifier. Finally, merge the sorted logs in order and store them in the result res. Finally, don’t forget to add the digital logs to res. See the code as follows:

Code

C++

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> res, digitLogs;
        vector<vector<string>> data;
        for (string log : logs) {
            auto pos = log.find(" ");
            if (log[pos + 1] >= '0' && log[pos + 1] <= '9') {
                digitLogs.push_back(log);
                continue;
            }
            data.push_back({log.substr(0, pos), log.substr(pos + 1)});
        }
        sort(data.begin(), data.end(), [](vector<string>& a, vector<string>& b) {
            return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);
        });
        for (auto &a : data) {
            res.push_back(a[0] + " " + a[1]);
        }
        for (string log : digitLogs) res.push_back(log);
        return res;
    }
};

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        int length = logs.length;
        for (int i = 1; i < length; i++) {
            String log = logs[i];
            int insertIndex = 0;
            for (int j = i - 1; j >= 0; j--) {
                String curLog = logs[j];
                if (compare(curLog, log) <= 0) {
                    insertIndex = j + 1;
                    break;
                }
                logs[j + 1] = logs[j];
            }
            logs[insertIndex] = log;
        }
        return logs;
    }

    public int compare(String log1, String log2) {
        String[] array1 = log1.split(" ");
        String[] array2 = log2.split(" ");
        String str1 = array1[1], str2 = array2[1];
        boolean isLetter1 = Character.isLetter(str1.charAt(0)), isLetter2 = Character.isLetter(str2.charAt(0));
        if (isLetter1 && isLetter2) {
            int space1 = log1.indexOf(' '), space2 = log2.indexOf(' ');
            String identifier1 = log1.substring(0, space1), identifier2 = log2.substring(0, space2);
            String letters1 = log1.substring(space1 + 1), letters2 = log2.substring(space2 + 1);
            if (letters1.compareTo(letters2) != 0)
                return letters1.compareTo(letters2);
            else
                return identifier1.compareTo(identifier2);
        } else if (isLetter1)
            return -1;
        else if (isLetter2)
            return 1;
        else
            return 0;
    }
}

############

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs, this::cmp);
        return logs;
    }

    private int cmp(String a, String b) {
        String[] t1 = a.split(" ", 2);
        String[] t2 = b.split(" ", 2);
        boolean d1 = Character.isDigit(t1[1].charAt(0));
        boolean d2 = Character.isDigit(t2[1].charAt(0));
        if (!d1 && !d2) {
            int v = t1[1].compareTo(t2[1]);
            return v == 0 ? t1[0].compareTo(t2[0]) : v;
        }
        if (d1 && d2) {
            return 0;
        }
        return d1 ? 1 : -1;
    }
}

// OJ: https://leetcode.com/problems/reorder-log-files
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> digitLogs, letterLogs;
        for (string &s : logs) {
            int i = 0;
            while (s[i] != ' ') ++i;
            if (isalpha(s[i + 1])) letterLogs.push_back(s.substr(i + 1) + " " + s.substr(0, i));
            else digitLogs.push_back(s);
        }
        sort(letterLogs.begin(), letterLogs.end());
        for (string &s : letterLogs) {
            int i = s.size() - 1;
            while (s[i] != ' ') --i;
            s = s.substr(i + 1) + " " + s.substr(0, i);
        }
        for (string &s : digitLogs) letterLogs.push_back(s);
        return letterLogs;
    }
};

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def cmp(x):
            a, b = x.split(' ', 1)
            return (0, b, a) if b[0].isalpha() else (1,)

        return sorted(logs, key=cmp)

############

class Solution(object):
    def reorderLogFiles(self, logs):
        """
        :type logs: List[str]
        :rtype: List[str]
        """
        letters = []
        nums = []
        for log in logs:
            logsplit = log.split(" ")
            if logsplit[1].isalpha():
                letters.append((" ".join(logsplit[1:]), logsplit[0]))
            else:
                nums.append(log)
        letters.sort()
        return [letter[1] + " " + letter[0] for letter in letters] + nums

function reorderLogFiles(logs: string[]): string[] {
    const isDigit = (c: string) => c >= '0' && c <= '9';
    return logs.sort((a, b) => {
        const end1 = a[a.length - 1];
        const end2 = b[b.length - 1];
        if (isDigit(end1) && isDigit(end2)) {
            return 0;
        }
        if (isDigit(end1)) {
            return 1;
        }
        if (isDigit(end2)) {
            return -1;
        }
        const content1 = a.split(' ').slice(1).join(' ');
        const content2 = b.split(' ').slice(1).join(' ');
        if (content1 === content2) {
            return a < b ? -1 : 1;
        }
        return content1 < content2 ? -1 : 1;
    });
}

impl Solution {
    pub fn reorder_log_files(mut logs: Vec<String>) -> Vec<String> {
        logs.sort_by(|s1, s2| {
            let (start1, content1) = s1.split_once(' ').unwrap();
            let (start2, content2) = s2.split_once(' ').unwrap();
            match (
                content1.chars().nth(0).unwrap().is_digit(10),
                content2.chars().nth(0).unwrap().is_digit(10),
            ) {
                (true, true) => std::cmp::Ordering::Equal,
                (true, false) => std::cmp::Ordering::Greater,
                (false, true) => std::cmp::Ordering::Less,
                (false, false) => content1.cmp(&content2).then(start1.cmp(&start2)),
            }
        });
        logs
    }
}

937 - Reorder Data in Log Files

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions