unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 791: Custom Sort String

link

We can use counting sort. While processing order left-to-right, if order[i] = c and c appears m times in s, we emit [c] * m.

Time: \mathcal{O}( |order| + |s| ), extra space: \mathcal{O}(|\texttt{alphabet-size}|).

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        s_map = {}
        for c in s:
            s_map[c] = s_map.get(c, 0) + 1
        
        perm = []
        for c in order:
            if c not in s_map:
                continue
            
            perm.extend([c] * s_map[c])
            del s_map[c]
        
        # Emit characters not in order
        for c in s_map:
            perm.extend([c] * s_map[c])
        
        return "".join(perm)

Since the alphabet only consists of lowercase English letters, we can keep a list of length 26 as the s_map.

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        def char(offset):
            return chr( ord('a') + offset )

        def offset(c):
            return ord(c) - ord('a')

        s_map = [0] * 26
        for c in s:
            s_map[offset(c)] += 1
        
        perm = []
        for c in order:
            i = offset(c)
            if s_map[i] == 0:
                continue
            
            perm.extend([c] * s_map[i])
            s_map[i] = 0
        
        # Emit characters not in order
        for i in range(26):
            if s_map[i] == 0:
                continue

            perm.extend([char(i)] * s_map[i])
        
        return "".join(perm)

tanvirdotzaman

,

Leave a comment