Problem
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.
Solution
java Arrays.sort() can take a customized comparator as the second parameter, then use stable sort algorithm merge sort to sort the array in O(M*N*longN) time, the M is the log length and the N is the total number of logs. For the comparator, we need to specify that: for letter logs, we compare content then identifier; for digit log, since merge sort is stable, digit logs are in the original order without us do anything.
We can do the sort faster by group the L letter logs and D digit logs, then sort letter logs only. So the time complexity is O(M*LlogL + D), the M is the cost of compare 2 letter logs lexicographically. LlogL is the cost of sort L letter logs with merge sort. Digit logs don't need to be sorted, so the cost is D. The space complexity is O(M*LogL + M*D) where logL is the space for the tree set and D is the space for the ArrayList.
import java.util.*;
class Solution {
public static void main(String...args) {
String[] logs = new String[] {"dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"};
Set<String> wordLog = new TreeSet<>((o1, o2) -> {
int idx1 = o1.indexOf(" ");
int idx2 = o2.indexOf(" ");
if(o1.substring(idx1 + 1).compareTo(o2.substring(idx2 + 1)) == 0) {
return o1.substring(0, idx1).compareTo(o2.substring(0, idx2));
} else {
return o1.substring(idx1 + 1).compareTo(o2.substring(idx2 + 1));
}
});
List<String> digitLog = new ArrayList<>();
for(String log : logs) {
int index = log.indexOf(" ");
if(Character.isDigit(log.charAt(index+1))) {
digitLog.add(log);
} else {
wordLog.add(log);
}
}
wordLog.stream().forEach(i -> System.out.print(i + ","));
digitLog.stream().forEach(i -> System.out.print(i + ","));
}
}
Time complexity O(MLlogL), space complexity O(MLogL + MD)
