791. Custom Sort String #

Problem #

order and str are strings composed of lowercase letters. In order, no letter occurs more than once.

order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted. More specifically, if x occurs before y in order, then x should occur before y in the returned string.

Return any permutation of str (as a string) that satisfies this property.

Example:Input:
order = "cba"
str = "abcd"
Output: "cbad"
Explanation:
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Note:

• order has length at most 26, and no character is repeated in order.
• str has length at most 200.
• order and str consist of lowercase letters only.

Problem Summary #

Strings S and T contain only lowercase characters. In S, every character appears only once. S has already been sorted according to some rule. We need to sort T according to the character order in S. More specifically, if x appears before y in S, then x should also appear before y in the returned string. Return any string T that satisfies the condition.

Solution Approach #

• The problem only requires the characters in T that are contained in S to be ordered, so we can first sort the characters in T that are contained in S, and then concatenate the other characters. The string S has a maximum length of 26. First, shift the indices of the characters in S left by 30, and store the shifted index values in a dictionary. Then sort the string T according to the index values in the dictionary. After processing, the indices corresponding to the characters that appear in S become negative numbers, while the indices of the characters that do not appear in S remain positive numbers. Therefore, after sorting, the characters that appear in S are arranged at the front in their original order, and the characters that do not appear in S are arranged after them in order.

Code #

package leetcode

import "sort"

func customSortString(order string, str string) string {
	magic := map[byte]int{}
	for i := range order {
		magic[order[i]] = i - 30
	}
	byteSlice := []byte(str)
	sort.Slice(byteSlice, func(i, j int) bool {
		return magic[byteSlice[i]] < magic[byteSlice[j]]
	})
	return string(byteSlice)
}