排序字符串列表的复杂性约束

Question

我需要对字符串列表进行排序，其中每个字符串的长度为k，并且每个字符串只包含字符{'a', 'b', 'c', 'd', 'e'}。
我确实有以下限制：

1. 我不能使用任何排序方法，包括python附带的方法。你知道吗
2. 比较两个字符串非常复杂O(k)。你知道吗
3. 排序不到位，需要返回新的排序列表。你知道吗
4. 空间复杂度是O(k)[w/o考虑长度的返回列表n]。你知道吗
5. 时间复杂度是O(n*k*(5^k))。你知道吗

函数接收lst, k，这是要排序的列表和列表中每个字符串的长度。我有两个方法string_to_int(), int_to_string()，它们将长度为k的字符串转换为[0,5^k)范围内的数字，反之亦然，这些方法是双射。这些方法的时间复杂度都是O(k)。你知道吗

我最好的尝试是：

def sort_strings(lst, k):
  int_lst = []
  for item in lst:
      int_lst.append(string_to_int(item))
  sorted_lst = []
  for i in range(5**k):
      if i in int_lst:
          sorted_lst.append(int_to_string(k, i))

  return sorted_lst 

但是这里我创建了int_lst，它的空间复杂度是O(n)，而不是O(k)。 有什么办法吗？你知道吗

Answer 1

你的时间限制太长了。这样就有足够的时间按顺序检查每个可能的长度为k的字符串，并将这些字符串与输入列表中的每个字符串进行比较。你知道吗

你能用它做什么？你知道吗

Answer 2

尝试重用int_list作为输出

    replace = 0

    for i in range(5 ** k):
        if i in int_list[replace:]:
            int_list[replace] = int_to_string(i, k)
            replace += 1

    return int_list

编辑：如果输入列表包含重复项，请考虑while i in int_list[replace:]:而不是if ....。你知道吗