Problem#
You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier .
There are two types of logs:
Letter-logs : All words (except the identifier) consist of lowercase English letters.Digit-logs : All words (except the identifier) consist of digits.
Reorder these logs so that:
The letter-logs come before all digit-logs .
The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
The digit-logs maintain their relative ordering.
Return the final order of the logs .
Examples#
Example 1:
1
2
3
4
5
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" .
Example 2:
1
2
Input: logs = [ "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" ]
Solution#
Method 1 – Custom Sorting#
Intuition#
Divide the logs into letter-logs and digit-logs. Letter-logs are sorted by their content and, if needed, by their identifier, while digit-logs retain their original sequence. This is possible because the type of log can be identified by the first character after the identifier.
Approach#
Separate each log into its identifier and the rest of its content.
Determine whether the content begins with a letter or a digit.
Group letter-logs and digit-logs into different lists.
Sort the letter-logs lexicographically by content, and by identifier if the contents are the same.
Combine the sorted letter-logs with the digit-logs, preserving the original order of digit-logs.
Return the final merged list.
We can use java’s String split function with limit: Java String split method .
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public :
vector< string> reorderLogFiles(vector< string>& logs) {
vector< string> let, dig;
for (auto & log : logs) {
int pos = log.find(' ' );
if (isdigit(log[pos + 1 ]))
dig.push_back(log);
else
let.push_back(log);
}
sort(let.begin(), let.end(), [](const string& a, const string& b) {
int i1 = a.find(' ' ), i2 = b.find(' ' );
string c1 = a.substr(i1 + 1 ), c2 = b.substr(i2 + 1 );
if (c1 != c2) return c1 < c2;
return a.substr(0 , i1) < b.substr(0 , i2);
});
let.insert(let.end(), dig.begin(), dig.end());
return let;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func reorderLogFiles (logs []string ) []string {
let := []string {}
dig := []string {}
for _ , log := range logs {
idx := 0
for i , c := range log {
if c == ' ' {
idx = i
break
}
}
if log [idx + 1 ] >= '0' && log [idx + 1 ] <= '9' {
dig = append(dig , log )
} else {
let = append(let , log )
}
}
sort .Slice (let , func (i , j int ) bool {
i1 := strings .IndexByte (let [i ], ' ' )
i2 := strings .IndexByte (let [j ], ' ' )
c1 := let [i ][i1 + 1 :]
c2 := let [j ][i2 + 1 :]
if c1 != c2 {
return c1 < c2
}
return let [i ][:i1 ] < let [j ][:i2 ]
})
return append(let , dig ... )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public String[] reorderLogFiles (String[] logs) {
List< String> let = new ArrayList<> (), dig = new ArrayList<> ();
for (String log : logs) {
int idx = log.indexOf (' ' );
if (Character.isDigit (log.charAt (idx + 1)))
dig.add (log);
else
let.add (log);
}
let.sort ((a, b) -> {
int i1 = a.indexOf (' ' ), i2 = b.indexOf (' ' );
String c1 = a.substring (i1 + 1), c2 = b.substring (i2 + 1);
if (! c1.equals (c2)) return c1.compareTo (c2);
return a.substring (0, i1).compareTo (b.substring (0, i2));
});
let.addAll (dig);
return let.toArray (new String[ 0] );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
fun reorderLogFiles (logs: Array<String>): Array<String> {
val let = mutableListOf<String>()
val dig = mutableListOf<String>()
for (log in logs) {
val idx = log.indexOf(' ' )
if (log[idx + 1 ].isDigit()) dig.add(log)
else let.add(log)
}
let.sortWith(Comparator { a, b ->
val i1 = a.indexOf(' ' )
val i2 = b.indexOf(' ' )
val c1 = a.substring(i1 + 1 )
val c2 = b.substring(i2 + 1 )
if (c1 != c2) c1.compareTo(c2)
else a.substring(0 , i1).compareTo(b.substring(0 , i2))
})
return (let + dig).toTypedArray()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List
class Solution :
def reorderLogFiles (self, logs: List[str]) -> List[str]:
let, dig = [], []
for log in logs:
idx = log. find(' ' )
if log[idx + 1 ]. isdigit():
dig. append(log)
else :
let. append(log)
let. sort(key= lambda x: (x[x. find(' ' ) + 1 :], x[:x. find(' ' )]))
return let + dig
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
pub fn reorder_log_files (logs: Vec< String> ) -> Vec< String> {
let mut let_logs = Vec::new();
let mut dig_logs = Vec::new();
for log in logs {
let idx = log.find(' ' ).unwrap();
if log.as_bytes()[idx + 1 ].is_ascii_digit() {
dig_logs.push(log);
} else {
let_logs.push(log);
}
}
let_logs.sort_by(| a, b| {
let i1 = a.find(' ' ).unwrap();
let i2 = b.find(' ' ).unwrap();
let c1 = & a[i1 + 1 .. ];
let c2 = & b[i2 + 1 .. ];
if c1 != c2 {
c1.cmp(c2)
} else {
a[.. i1].cmp(& b[.. i2])
}
});
let_logs.extend(dig_logs);
let_logs
}
}
Complexity#
⏰ Time complexity: O(n log n), where n is the number of logs (sorting letter-logs dominates).
🧺 Space complexity: O(n), for storing separated logs.