Реализация алгоритма для определения того, имеет ли строка все уникальные символы

Контекст: я CS n00b, работающий на моем пути через «Cracking the Coding Interview». Первая проблема требует «реализовать алгоритм, чтобы определить, имеет ли строка все уникальные символы». Моя (вероятно наивная) реализация такова:

def isUniqueChars2(string): uchars = [] for c in string: if c in uchars: return False else: uchars.append(c) return True 

Автор предлагает следующую реализацию:

 def isUniqueChars(string): checker = 0 for c in string: val = ord(c) - ord('a') if (checker & (1 << val) > 0): return False else: checker |= (1 << val) return True 

Что делает реализацию автора лучше, чем моя (FWIW, авторское решение было на Java, и я преобразовал его в Python – это мое решение, которое невозможно реализовать на Java)? Или, в более общем плане, что желательно в решении этой проблемы? Что не так с подходом, который я принял? Я предполагаю, что есть некоторые фундаментальные концепции CS (которые я не знаю), которые важны и помогают информировать о выборе того или иного подхода к этой проблеме.

7 Solutions collect form web for “Реализация алгоритма для определения того, имеет ли строка все уникальные символы”

Вот как я писал бы это:

 def unique(s): return len(set(s)) == len(s) 

Строки повторяются, поэтому вы можете передать свой аргумент напрямую, чтобы set() чтобы получить набор символов из строки (которая по определению не будет содержать дубликатов). Если длина этого набора совпадает с длиной исходной строки, то у вас есть совершенно уникальные символы.

Ваш нынешний подход прекрасен, и, на мой взгляд, он намного более Pythonic и читабельный, чем версия, предложенная автором, но вы должны изменить uchars как набор вместо списка. Наборы имеют O (1) критерий принадлежности, поэтому c in uchars будет значительно быстрее в среднем, если uchars – это набор, а не список. Таким образом, ваш код можно записать следующим образом:

 def unique(s): uchars = set() for c in s: if c in uchars: return False uchars.add(c) return True 

Это будет действительно более эффективно, чем моя версия, если строка большая, и есть дубликаты раньше, потому что она будет короткозамкнута (выйдите, как только будет найден первый дубликат).

Красиво лучше, чем уродливое.

Твой подход прекрасен. Это python, когда есть возможность сделать что-то в бай-дионе. (Твой тоже красивее :)). Но если вы действительно хотите, чтобы он был более питоническим и / или ускорил его, вы могли бы использовать набор, как описал ответ FJ.

Второе решение просто очень сложно понять и понять.

(PS, dict – это встроенный тип. Не переопределяйте его: p. И string – это модуль из стандартной библиотеки.)

Ваше решение не является неправильным, но ваша переменная dict на самом деле не является словарем, что означает, что он должен выполнять линейный поиск для проверки символа. Решение из книги выполняет проверку в постоянное время. Я скажу, что другое решение является нескромно нечитаемым, потому что оно использует установку битов в число, чтобы проверить, является ли символ уникальным или нет

Решение, которое вы перевели с Java на Python, называется так называемым алгоритмом «бит-скручивание». Идея состоит в том, что целое число можно обрабатывать несколькими способами: одним, как числом. Два, как набор бит (32 выкл., Или 64, или что-то-вы). Алгоритм бит-twiddles, говоря, что каждый бит представляет присутствие или отсутствие определенного символа – если n-й бит равен 0, он устанавливает его. Если это 1, символ, который соответствует биту, уже существует, поэтому мы знаем, что нет уникальных символов.

Однако, если вам не нужна эффективность, избегайте алгоритмов бит-скручивания, поскольку они не настолько очевидны в том, как они работают как не-бит-скриды.

 str = raw_input("Enter string: ") def isUnique(): test_dict = dict() is_unique = True for c in str: if(not test_dict.get(c, False)): test_dict[c] = c else: is_unique = False break if is_unique: return "String is unique" else: return "String is not unique" print(isUnique()) 

ваша реализация принимает O (n2), автор берет O (n). В вашей реализации «если c в uchars:», когда он проверяет, есть ли c в этом массиве, он должен пройти весь массив, для этого требуется время. Так что ваш не лучше, чем авторский …

Решение 1:

 def is_unique(string): if len(string) > 128: return False unique_tracker = [False] * 128 for char in string: if unique_tracker[ord(char)] == False: unique_tracker[ord(char)] = True else: return False return True 

Решение 2:

 def is_unique_bit(string): if len(string) > 128: return False unique_tracker = 0 for char in string: ascii_val = ord(char) if (unique_tracker & (1 << ascii_val)) > 0: return False unique_tracker |= (1 << ascii_val) return True 
  • Понимание того, как создать кучу в Python
  • Свойства класса и __setattr__
  • правила для пули и юникода
  • Неожиданный результат от оператора `in` - Python
  • Недокументированная максимальная длина URL-адреса URL-адреса?
  • Блокировать запросы от * .appspot.com и принудительно настраивать собственный домен в Google App Engine
  • Подключить четыре игры к сетке
  • Как изменить записи списка во время цикла?
  • числа треугольников в python
  • доступ к Google с помощью python
  • Можно ли использовать «делегирование полномочий домена» с помощью gdata-python-client?
  •  
    Interesting Posts for Van-Lav

    Поиск самого длинного списка в списке списков в Python

    Вызов staticmethod внутри инициализации контейнеров уровня класса

    Объединение двух сетевых карт в networkx с помощью уникальных ярлыков

    Переупорядочение элементов в QTreeWidget с перетаскиванием в PyQt

    Должен ли один снижать код сервера, когда он находится в производстве?

    Использование цикла в Python для обозначения переменных

    Получить верхнюю часть n в каждой группе DataFrame в pyspark

    Как передать изображения в ответ сервера с помощью JSON? Base64?

    .csv между каждой буквой на выходе

    Как определить, работает ли процесс с использованием Python для Win и MAC

    Операции «Boolean» в Python (т.е.: и / или операторы)

    Как вы контролируете доступ пользователей к записям в базе данных ключа?

    Как я мог «слушать» звуки на внутреннем динамике материнской платы

    Подмножество данных в Python

    Удаление символов, отличных от ASCII, из строки с использованием python / django

    Python - лучший язык программирования в мире.