# 字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。
#
# S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。
#
# 返回任意一种符合条件的字符串T。
#
# 示例:
# 输入:
# S = "cba"
# T = "abcd"
# 输出: "cbad"
# 解释:
# S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a".
# 由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。
# 注意:
#
# S的最大长度为26，其中没有重复的字符。
# T的最大长度为200。
# S和T只包含小写字符。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/custom-sort-string
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    # Solution 1: 利用hashmap 存下 T中的所有字符，遍历 S 中的所有字符进行重组
    # def customSortString(self, S: str, T: str) -> str:
    #     charset = {}
    #     for c in T:
    #         charset[c] = charset.get(c, 0) + 1
    #
    #     output = []
    #     for c in S:
    #         if c in charset:
    #             times = charset.get(c, 0)
    #             output += ([c] * times)
    #             charset.pop(c)
    #
    #     for c, times in charset.items():
    #         output += ([c] * times)
    #
    #     return "".join(output)

    # Solution 2: 利用 Hashmap 存入 优先级，越靠前优先级越高
    def customSortString(self, S: str, T: str) -> str:
        priorities = {}
        for i, c in enumerate(S):
            priorities[c] = i

        return "".join(sorted(list(T), key=lambda c: priorities.get(c, 27)))


if __name__ == '__main__':
    s = Solution()
    assert s.customSortString("cba", "abcd") == "cbad"
    assert s.customSortString("cba", "") == ""
