LeetCode 791. Custom Sort String - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/custom-sort-string/


First I tried to use lambda for Arrays.sort(T[]), but it doesn't work that way.

So I come up with 3 arrays of the length of 27 which covers all the chars.

the
count: char -> occurrence
map:   char -> i index
seq:     index i -> char

this way, you can easily assemble the answer.

From their sorted sequence, with given char and the respective occurrence. all within your reach in O(1).

That's crazily fast! So let's do it!

	class Solution {
	String customSortString(String S, String T) {
	// filter abnormal cases
	if (T == null || T.length() == 0) {
	return T;
	}
	if (S == null || S.length() == 0) {
	return T;
	}
	map = new int[27];
	sequence = new int[27];
	for (int i = 0; i < 27; i++) {
	map[i] = -1;
	sequence[i] = -1;
	}
	for (int index = 0; index < S.length(); index++) {
	map[S.charAt(index) - 'a'] = index;
	sequence[index] = S.charAt(index) - 'a';
	}
	count = new int[27];
	for (int i = 0; i < T.length(); i++) {
	count[T.charAt(i) - 'a']++;
	}
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = 0; i < T.length() && sequence[i] != -1; i++) {
	int index = sequence[i];
	char currentChar = (char) (index + 'a');
	for (int times = 0; times < count[index]; times++) {
	stringBuilder.append(currentChar);
	}
	count[index] = 0;
	}
	for (int i = 0; i < count.length; i++) {
	if (count[i] > 0) {
	for (int j = 0; j < count[i]; j++) {
	stringBuilder.append((char) (i + 'a'));
	}
	}
	}
	// return the final result
	return stringBuilder.toString();
	}
	int[] map;
	int[] sequence;
	int[] count;
	}

view raw LC 791. Custom Sort String - Weekly Contest 73 - LeetCode.java hosted with ❤ by GitHub