Всем привет! Я написал небольшую статью, возможно будет интересно:
Swift String Iterator // Собеседование, работа над ошибками
У вас отстойная реализация
На свифте оно выглядело бы так:
func isPalindrom(_ str: String) -> Bool {
var str = str.lowercased().components(separatedBy: CharacterSet(charactersIn: "abcdefghijklmnopqrstuvwxyz0123456789").inverted).joined()
while true {
switch str.count {
case 0...1:
return true
case 2...Int.max where str.removeFirst() == str.removeLast():
break
default:
return false
}
}
}
P.S. И собеседование тоже отстойное
Вы не учли требования ни по памяти, ни по времени.
Использование массива, приведение к lowercased, joined. Это дополнительная память, и как минимум лишний проход по всей строке.
Затем removeFirst это линейное время.
Итого вы использовали дополнительно O(n) памяти и O(n * n) времени.
Может решение и выглядит компактным, но оно очень не эффективно.
Так я и говорю что отстойное собеседование, лучше проще да лучше и на собеседовании я бы так и сказал
Часто в крупных компаниях ты или решаешь как надо или не работаешь)
А так, задача очень искуственная и на практике редко можно встретить. Но иногда очень важно писать сразу реально очень эффективный код, когда пишешь продукт для тучи народа. Так что, в таких собеседованиях есть свой смысл.
Да, я сталкивался с таким)
Но с другой стороны во времена когда компании уровня Микрософт пишут на ReactNative считать количество проходов по строке это как то, ну не знаю, совсем бред.
Не нравится мне перебор characters в любом случае. Не проверял в коде но исходная идея в моем случае было бы использование слов. Т.е. - 1. oпределяем string.count. 2. Получаем две substrings - половины, в случае нечетного количества string.count не включаем центральный character. (В ДНК палиндромы имеют четное количество букв). Используем .inverted для одной из половин и затем сравниваем половины одну нативную и другую инвертированную на наличие их равенства.
Было бы более интересно задание на функцию проверяющую на наличие внутри заданного string палиндромов с длинной в заданном диапазоне, с позиции времени.
Здравствуйте! Интересная идея) Вы не биолог случайно?
-
С characters нужно работать аккуратно. Если вы просто вызовите characters, то получите сразу O(n) перебор и копию в виде массива O(n) памяти. Если я ничего не путаю, конечно;
-
На самом деле вы забыли про пробелы. К примеру, палиндром: Madam, I’m Adam.
Если удалять пробелы из строки - будет копия и мы не выполним требование по памяти O(1); -
И если вы посмотрите выводы, то поймете что в этой задаче центр палиндрома - не центр строки.
Было бы более интересно задание на функцию проверяющую на наличие внутри заданного string палиндромов с длинной в заданном диапазоне, с позиции времени.
Проблема в том, что тут есть символы которые не нужно учитывать и их нельзя вырезать.
Асимптотика решения всё равно будет O(n) в лучшем случае, так как нам нужно перебрать каждый символ строки. Вы уже говорите о строковых алгоритмах, сейчас изучаю их на втором семестре.
Биолог.
Если есть символы которые нельзя учитывать то можно их всех заменить на “” (в исходном стринг или позже в ее половинах) используя .replacingOccurrences(of: “Any” , with: “” ). В остальном все так же. Не знаю что будет со временем и памятью, т.е. как реализована .replacingOccurrences(of: , with: ).
Биолог это очень здорово) я пока учился была интересная задача на сравнение цепочек нуклеотидов с использованием быстрого преобразования Фурье. Интересно, но сложно)
На самом деле replacingOccurrences может не сделать копию, если строка больше никому не нужна. Что-то вроде “Copy on write”, но вроде незачем копировать если только 1 ссылка. Но это лишь догадка) Удаление любого символа из строки (массива) это O(n), так как нужно сдвинуть все остальные после него. В худшем случае O(n * n). Хотя там может использоваться не массив, а например, связный список. Так как всё равно нет рандомного доступа к символам строки.
Это удобное решение с replacingOccurrences, но оно не прошло бы) Требования были другие и тут тоже проверяют знания структур и работы с памятью.
Меня тоже этот момент смутил, ещё в методе isCaseInsensitiveEqual происходит преобразование в строку и потом строки сравниваются.
Проще сразу строку мучать:
func isPalindrom2(_ str: String) -> Bool {
let set = CharacterSet(charactersIn: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLKMNOPQRSTUVWXYZ0123456789")
var range = str.startIndex..<str.endIndex
while range.lowerBound < range.upperBound {
var left: Substring!
var right: Substring!
while let r = str.rangeOfCharacter(from: set, range: range) {
range = r.upperBound..<range.upperBound
left = str[r]
break
}
while let r = str.rangeOfCharacter(from: set, options: .backwards, range: range) {
range = range.lowerBound..<r.lowerBound
right = str[r]
break
}
guard left != nil && right != nil else { break }
guard left == right || left.lowercased() == right.lowercased() else { return false }
}
return true
}
И значительно быстрее:
P.S. Тестировал строкой в 1000000 символов
В плане общего решения у вас вроде тоже самое происходит, только вместо моих переборов за вас это делает rangeOfCharacter.
Не понимаю зачем while, если сразу идёт break.
В строку приходится приобразовывать, так как у Character не нашёл способа сравнения без учёта регистра. У вас тоже тут lowercased копию делает, лучше использовать именно сравнение. Там возможно это без копии происходит.
Тесты тоже сделал, вроде получается одинаково. Я не смог нормально реализовать, чтобы тестовые данные использовались одинаковые и оптимизаций строк не было. У вас возможно как раз это) поменяйте местами методы, будет разница? или по одному.
Сейчас нет времени разбираться, а так интересно)
У меня моё решение на 1_000_000 выигрывает немного) а на больших цифрах начинает потихоньку проигрывать. Возможно из-за преобразования в строку, или что-то ещё.
Тут сложно что то лучше придумать.
Break если одна из строк nil.
CaseInsensitiveCompare работает медленнее чем просто сравнение строк, в моём искусственном тесте по крайней мере, по этому я их сначала просто сравниваю а потом в нижнем регистре.
Нет разницы и по одному такой же результат, видимо разница из за кривого теста.
Вероятно что rangeOfCharacter более эффективен чем просто перебор.
Из моего небольшого опыта использование string.range(of: ) эффективнее чем простой перебор массивов.
Если есть два массива strings и надо найти сколько раз string из одного массива встречается в strings другого, то решени в лоб с перебором двух массивом в моем случае было порядка четырех раз медленнее чем поиск range of string из первого массова в строке составленной из strings второго массива.
Благодаря вам наткнулся на то что, можно итератор использовать в for in, вроде этого:
struct StringDownIterator: IteratorProtocol, Sequence {
private let str: String
private let count: Int
private var current = 0
init(_ str: String) {
self.str = str
count = str.count
}
mutating func next() -> Character? {
guard -current < count else { return nil }
current -= 1
return str[str.index(str.endIndex, offsetBy: current)]
}
}
extension String {
func makeDownIterator() -> StringDownIterator {
return StringDownIterator(self)
}
}
let iter = "ABC".makeDownIterator()
for c in iter {
print(c) // C B A
}
Прям как в es6 (только там for of)
Добавил тесты и ваше решение в репозитой. Github.
Посмотрите, если интересно. Там действительно уходит время на инициализацию строки, пришлось для этого отдельный тест создать чтобы это время не учитывалось в остальных реальных тестах.
While внутри while там можно смело заменить на if, я это тоже добавил как альтернативное решение. Также использовал уже готовые множества символов, это не совсем правильно в рамках задачи, но часто просто буквы нужны.
Также поразбирался, получается у вас могут быть случаи с O(n) доп. памятью. Когда у нас вся строка, кроме центрального символа состоит из корректных символов. Мы дойдем до центра и lowercased() создаст 2 строки из Substring. А это уже похоже на доп. память.
CaseInsensitiveCompare забыл проверить)