937. Reorder Data in Log Files

Medium

Problem:

Reorder the logs based on the following rules:

The identifier, which is the first part of the log, doesn't impact the order.
Letter-logs should be ordered before those digit-logs.
When the content of the word logs is identical, the logs should then be sorted based on their identifier.
Digit-logs should remain in the original input order.

Note: If their contents are the same, then sort them lexicographically by their identifiers.

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"]
Explanation: The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig". The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

https://leetcode.com/problems/reorder-data-in-log-files/

What to learn:

set doesn't preserve order of insertion, but a list does.
The loop for tuples in the following solution is better than the one in the first solution:
```
for _, _, i in new_arr:  
    result_arr.append(logs[i])
```
Python's sort function allows for complex sorting rules by returning tuples from the key function. If the key function -- in the last solution, lambda -- returns a tuple, then sort will sort by the elements of the tuple in order - first sorts all elements primarily according to the first element of the tuple. This is sometimes referred to as "lexicographical" or "dictionary" order. In other words, this code is sorting the strings in letters first by the second word in each string, and then (in the case of ties) by the first word in each string.

Solutions:

Divide the provided list into digits and letters.
Sort the letters excepting the identifier.
Return the entire list.

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        ordered_set = set()
        num_list = []
        new_arr = []
        result_arr = []
        # Separate letter-logs and digit-logs
        # Save indices
        arr = [item.split() for item in logs]
        for idx, elem in enumerate(arr):
            # if the log contains a digit, it's a digit-log
            if elem[1].isdigit():
                num_list.append(idx)
            # otherwise, it's a letter-log
            else:
                ordered_set.add(idx)
        # tuple: (identifier, log_content, index)
        for i in ordered_set:
            log_parts = logs[i].split(" ", 1)  # split only on the first space
            identifier = log_parts[0]
            content = log_parts[1]
            new_arr.append((identifier, content, i))

        # Sort by identifier and log content
        new_arr.sort(key=lambda x: (x[1], x[0]))  # sort primarily by content, then by identifier

        # Letter-logs ordering
        for tup in new_arr:
            result_arr.append(logs[tup[2]])

        # Digit-logs ordering
        for i in num_list:
            result_arr.append(logs[i])
        return result_arr

Better approach

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letters, digits = [], []
        for log in logs:
            if log.split()[1].isdigit():
                digits.append(log)
            else:
                letters.append(log)
        letters.sort(key=lambda x: x.split()[1:], x.split()[0]))
        return letters + digits

Here's how it works:

# s = ['2 A', '1 B', '4 C', '1 A']
def func(x):
    return x.split()[1], x.split()[0]
sorted(s)        # ['1 A', '1 B', '2 A', '4 C']
s.sort(key=func) # ['1 A', '2 A', '1 B', '4 C']

func is a function that takes a string x as input. This string is expected to contain words separated by spaces.
x.split()[1] and x.split()[0] are used to split the input string x into a list of words. [1] and [0] are the indices used to access the second word and first word in the list respectively.
func returns a tuple of two elements: the second word in the string, and then the first word in the string.
s.sort(key=func) sorts the list s in place. The key parameter is used to specify a function of one argument that is used to extract a comparison key from each element in s. In this case, it's using func as the key, meaning it's sorting the strings primarily by their second word, and then by their first word.

In other words, this code is sorting the strings in s first by the second word in each string, and then (in the case of ties) by the first word in each string.

If func returned a tuple with more than two elements, sort would continue this process, comparing the next element in the tuple only if all the previous elements were equal. This lets you sort by as many criteria as you want, simply by extending the tuple returned by your key function.

Last updated 2 years ago