791. Custom Sort String - cocoder39/coco39_LC GitHub Wiki

791. Custom Sort String

Option 1: custom sort using lambda

O(N * logN)

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        order_map = {char: i for i, char in enumerate(order)}
        sorted_s = sorted(s, key=lambda char: order_map.get(char, 100 + ord(char)))
        return ''.join(sorted_s)

Option 2: leverage sorted string to achieve O(N)

note: tricky part is to reset counter once a char has been applied

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        counter = collections.Counter(s)

        res = ''
        for ch in order:
            if ch in counter:
                res += ch * counter[ch]
                counter[ch] = 0
        
        for ch in s:
            if counter[ch] > 0:
                res += ch * counter[ch]
                counter[ch] = 0
        return res