Сортировка строк по некоторому формату

Question

У меня есть строка, которая должна быть отсортирована на основе sort_fmt. Пример: если строка 'abdcdfs' и sort_fmt 'dacg'. После сортировки вывод должен быть 'ddacfbs'. Как видите, во входной строке могут быть символы, которых нет в строке заказа и наоборот. Символы входной строки, которых нет в строке заказа, должны находиться в конце строки вывода в любом порядке.

Вот что я написал. Это работает, это O (n * m) algo. Мне было интересно, есть ли лучшие и более короткие способы сделать это? Может быть, использовать itertools?

def sort_str(s, sort_fmt):
    sorted_str = ''
    str_hash   = dict()

    # O(n)
    for ch in s:
        if ch in str_hash:
            str_hash[ch] += 1
        else:
            str_hash[ch] = 1

    # O(m) + O(1) where m<=n
    for ch in sort_fmt:
        if ch in str_hash:
            cnt = str_hash[ch]
            sorted_str += cnt * ch

    # O(n)
    for ch in s:
        if ch not in sort_fmt:
            sorted_str += ch
    return sorted_str


if __name__ == '__main__':
    print sort_str('abdcdfs', 'dacg')

Answer 1

Вы пытаетесь реализовать подсчет сортировки , который действительно равен O (n) при определенных условиях.Однако ваша реализация имеет две ошибки в конце, которые означают, что фактическая временная сложность вашей реализации составляет O (n ² + n * m):

for ch in s:
    if ch not in sort_fmt:  # <--- "in" requires a linear search. O(n*m)
        sorted_str += ch    # <--- Ouch! Concatenation! O(n^2)

• ВыПостроение результата неэффективно, потому что вы используете конкатенацию в цикле.
• Использование in для строки является линейным по длине строки, и вы делаете это в цикле.

Попробуйте вместо этого.Требуется Python 2.7 или новее из-за использования collections.Counter, но Counter можно легко заменить на defaultdict для более старых версий Python):

from collections import Counter

def sort_str(s, sort_fmt):
    counter = Counter(s)
    d = set(sort_fmt)
    result = ''.join(c * counter[c] for c in sort_fmt)
    result += ''.join(c for c in s if c not in d)
    return result

if __name__ == '__main__':
    print sort_str('abdcdfs', 'dacg')

Вот более краткий способчтобы получить желаемый результат, если вы отбросите требование, чтобы оно было O (n):

>>> d = dict((v,k) for (k,v) in enumerate('dacg'))
>>> sorted('abdcdfs', key = lambda c:d.get(c, len(d)))
['d', 'd', 'a', 'c', 'b', 'f', 's']

Answer 2

Я не уверен насчет сложности сортировки. Это работает

def sort_str(s, frmt):
    l = len(frmt)
    return sorted(s, key = lambda x: frmt.index(x) if x in frmt else l)