791. 自定义字符串排序

题目描述：

给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 满足这个性质的 s 的任意一种排列 。

示例 1：

输入: order = "cba", s = "abcd"
输出: "cbad"
解释: 
“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。

示例 2：

输入: order = "cbafg", s = "abcd"
输出: "cbad"

提示：

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

---

解题分析及思路：

思路：

本题可以使用哈希表的方式来解决

首先我们可以统计 s 中每个字符出现的次数，然后遍历 order 中的字符，将 s 中的字符按照 order 中的顺序进行排列，最后将 s 中剩余的字符按照顺序排列即可。

func customSortString(order string, s string) string {
	sMap := make(map[uint8]int)
	for index := range s {
		sMap[s[index]] = sMap[s[index]] + 1
	}
	var result []uint8
	for index := range order {
		if v, ok := sMap[order[index]]; ok && v > 0 {
			for i := 0; i < v; i++ {
				result = append(result, order[index])
			}
			sMap[order[index]] = 0
		}
	}
	for k, v := range sMap {
		for i := 0; i < v; i++ {
			result = append(result, k)
		}
	}
	return string(result)
}

复杂度：

• 时间复杂度：O(M + N)，其中 M 是 order 的长度,其中 N 是 s 的长度。
• 空间复杂度：O(N)，其中 N 是 s 的长度。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.9 MB,击败了37.50% 的Go用户