Вы можете перебрать setA
от самой короткой строки до самой длинной и добавить данную строку в setC
, только если ни одна из возможных подстрок строки уже находится в setC
. Вы можете сгенерировать все возможные подстроки из строки, перебирая начальный индекс по длине строки и перебирая размер подстроки от 1 до оставшейся длины строки из текущего начального индекса, а затем используя начальный индекс и длина подстроки для нарезки строки:
setC = set()
for s in sorted(setA, key=len):
if not any(s[i: i + n + 1] in setC for i in range(len(s)) for n in range(len(s) - i)):
setC.add(s)
setC
становится:
{'AAB'}
Это улучшает общую сложность времени с O (n ^ 2) вашего решения O (n log n) .
Нет, определенно нет. Delphi идиома здесь использовать целые числа. Не борись с языком. В 32-битной среде у вас не будет больше элементов в списке, за исключением случаев, когда вы попытаетесь создать растровое изображение.
Давайте проясним: каждый программист, которому придется использовать ваш код, будет ненавидеть вас за использование кардинал вместо целого числа.
Беззнаковые целые числа почти всегда доставляют больше хлопот, чем они того стоят, потому что в какой-то момент вы обычно смешиваете целые числа со знаком и без знака в выражениях. Это означает, что тип должен быть расширен (и, возможно, иметь снижение производительности), чтобы получить правильную семантику (в идеале компилятор делает это в соответствии с определением языка), иначе вам нужно быть очень осторожным при проверке диапазона.
Возьмем, например, C / C ++: size_t
- это тип целого числа для размеров и распределения памяти, он не имеет знака, но ptrdiff_t
- это тип смещения, которое вы получаете, когда вы вычитайте один указатель из другого, и обязательно подписывайте. Хотите знать, сколько элементов вы размещены в массиве? Возможно, вы вычли адрес первого элемента
из адреса последнего элемента + 1
и поделили на размер sizeof (тип элемента)
? Что ж, теперь вы просто смешали целые числа со знаком и без знака.
Что касается вашего заявления о том, что «Я думаю, что в целом это хороший принцип - всегда использовать наименее общий (а значит, самый особенный) тип». - на самом деле, я думаю, что это хороший принцип - использовать тип данных, который вызовет у вас наименьшее беспокойство и Проблема.
Обычно для меня это подписанное int, поскольку:
Но это действительно проблема стиля. Если «чистота» кода важнее для вас, чем краткость кода, Ваш метод лучше всего (с модификациями, чтобы поймать крайние случаи). Сам я предпочитаю краткость, так как крайние случаи имеют тенденцию загромождать код и уменьшать понимание.
Мораль: используйте итераторы и foreach
, когда можете, потому что это полностью исключает этот вопрос.
Не.
Это не просто идет вразрез с идиомой программирования, это явный запрос к компилятору использовать арифметику без знака, которая либо склонна к аномальному поведению (если вы не t защита от переполнений) или от несущественных исключений времени выполнения (если вы защитите от переполнений, временное переполнение будет фатальным, например, если вычесть перед добавлением, даже если конечный результат положительный, и я имею в виду уровень кода операции ЦП упорядочение операций, которые могут не иметь тривиального отношения к тому, что у вас есть в вашем коде).
Имейте в виду, что «unsigned» не не переводит в «положительное», оно переводится как «не есть знак ", который отличается. Термин «без знака» был выбран не зря (и назвал его «Кардинал»). в Delphi было плохим выбором IMO).
Типы без знака предназначены для необработанных спецификаций хранения, побитовых операций, кода ASM, встроенных контроллеров и других специальных применений. Когда вы занимаетесь программированием высокого уровня, вы должны забыть, что когда-либо слышали о неподписанных типах.
Граничные условия часто представляют проблемы. Разрешение на тип, который может стать отрицательным, может просто сдвинуть проблему. Возможно, это смещает его так, что его легче отлаживать, а может и нет. Я начал использовать целые числа для подсчета таких циклов, но позже переключился на кардиналы, чтобы помочь мне отлавливать ошибки.