В Python набор считается как буфер?

Question

Я работаю через Крекинг кодирвоание интервью (4-е издание), и один из вопросов заключается в следующем:

Разработка алгоритма и написать код для удаления дубликатов символов в строке без использования какого-либо дополнительного буфера , ПРИМЕЧАНИЕ. Одна или две дополнительные переменные являются точными. Дополнительной копией массива нет.

Я написал следующее решение, которое удовлетворяет все случаи испытаний, указанных автор:

def remove_duplicate(s): 
    return ''.join(sorted(set(s))) 

print(remove_duplicate("abcd")) // output "abcd" 
print(remove_duplicate("aaaa")) // output "a" 
print(remove_duplicate("")) // output "" 
print(remove_duplicate("aabb")) // output "ab" 

ли мое использование набора в моем счете решения, как использование дополнительного буфера, или мое решение адекватно? Если мое решение не будет адекватным, что было бы лучшим способом сделать это?

спасибо!

Answer 1

Только человек, управляющий вопросом или оценивающий ответ, мог бы точно сказать, но я бы сказал, что набор считается буфером.

Если в строке нет повторяющихся символов, длина набора будет равна длине строки. На самом деле, поскольку набор имеет значительные накладные расходы, так как он работает с хэш-списком, набор, вероятно, займет больше памяти, чем строка. Если строка содержит Unicode, количество уникальных символов может быть очень большим.

Если вы не знаете, сколько уникальных символов находится в строке, вы не сможете предсказать длину набора. Возможная длинная и, вероятно, непредсказуемая длина множества заставляет его считаться буфером - или, что еще хуже, учитывая возможную длину, превышающую длину строки.

Answer 2

Чтобы следить за комментарием v.coder, я переписал код, на который он (или она) ссылался на Python, и добавил некоторые комментарии, чтобы попытаться объяснить, что происходит.

def removeduplicates(s): 
    """Original java implementation by 
      Druv Gairola (http://stackoverflow.com/users/495545/dhruv-gairola) 
     in his/her answer 
      http://stackoverflow.com/questions/2598129/function-to-remove-duplicate-characters-in-a-string/10473835#10473835 
     """ 
    # python strings are immutable, so first converting the string to a list of integers, 
    # each integer representing the ascii value of the letter 
    # (hint: look up "ascii table" on the web) 
    L = [ord(char) for char in s] 

    # easiest solution is to use a set, but to use Druv Gairola's method... 
    # (hint, look up "bitmaps" on the web to learn more!) 
    bitmap = 0 
    #seen = set() 

    for index, char in enumerate(L): 
     # first check for duplicates: 
     # number of bits to shift left (the space is the "lowest" 
     # character on the ascii table, and 'char' here is the position 
     # of the current character in the ascii table. so if 'char' is 
     # a space, the shift length will be 0, if 'char' is '!', shift 
     # length will be 1, and so on. This naturally requires the 
     # integer to actually have as many "bit positions" as there are 
     # characters in the ascii table from the space to the ~, 
     # but python uses "very big integers" (BigNums? I am not really 
     # sure here..) - so that's probably going to be fine.. 
     shift_length = char - ord(' ') 

     # make a new integer where only one bit is set; 
     # the bit position the character corresponds to 
     bit_position = 1 << shift_length 

     # if the same bit is already set [to 1] in the bitmap, 
     # the result of AND'ing the two integers together 
     # will be an integer where that only that exact bit is 
     # set - but that still means that the integer will be greater 
     # than zero. (assuming that the so-called "sign bit" of the 
     # integer doesn't get set. Again, I am not entirely sure about 
     # how python handles integers this big internally.. but it 
     # seems to work fine...) 
     bit_position_already_occupied = bitmap & bit_position > 0 

     if bit_position_already_occupied: 
     #if char in seen: 
      L[index] = 0 
     else: 
      # update the bitmap to indicate that this character 
      # is now seen. 
      # so, same procedure as above. first find the bit position 
      # this character represents... 
      bit_position = char - ord(' ') 

      # make an integer that has a single bit set: 
      # the bit that corresponds to the position of the character 
      integer = 1 << bit_position 

      # "add" the bit to the bitmap. The way we do this is that 
      # we OR the current bitmap with the integer that has the 
      # required bit set to 1. The result of OR'ing two integers 
      # is that all bits that are set to 1 in *either* of the two 
      # will be set to 1 in the result. 

      bitmap = bitmap | integer 
      #seen.add(char) 

    # finally, turn the list back to a string to be able to return it 
    # (again, just kind of a way to "get around" immutable python strings) 
    return ''.join(chr(i) for i in L if i != 0) 


if __name__ == "__main__": 
    print(removeduplicates('aaaa')) 
    print(removeduplicates('aabcdee')) 
    print(removeduplicates('aabbccddeeefffff')) 
    print(removeduplicates('&%!%)(FNAFNZEFafaei515151iaaogh6161626)([][][ ao8faeo~~~````%!)"%fakfzzqqfaklnz'))