Я знаю, что вы собираетесь сказать - опять же, проверка перестановки для 2 входных строк - такой простой вопрос собеседования по кодированию, зачем беспокоиться?
Что ж, на мой взгляд, и как многие из вас могут согласиться, иногда решение проблемы - это еще не конец. Что важнее:
- Как вы можете быть уверены, что это правильное решение?
- Как вы можете решить, является ли решение хорошим или даже оптимальным?
Исходя из этого, у нас есть эта статья. Итак, начнем!
Проблема
Учитывая две строки, предоставьте метод, чтобы решить, является ли одна перестановкой другой.
В переводе на язык программирования написание вида:
Input: 2 strings strA, strB. (string) Output: is strA permutation of strB? (true/false)
Просто как тот. Но ... вы можете задаться вопросом
Что такое «перестановка»?
Я знаю, не смейтесь. Многие люди не привыкли к этому термину, особенно если вы не используете его на повседневной основе, или если вы не являетесь носителем английского языка (возможно), или если вы сейчас не на уроке математики.
Во всяком случае, согласно Wiki:
Перестановка относится к действию размещения всех членов набора в некую последовательность или порядок, или, если набор уже упорядочен, переупорядочивая (переупорядочивая) его элементы.
Например: набор {1,2,3} будет иметь 6 различных перестановок, таких как (1,2,3), (1,3,2), (2,1,3 ), (2,3,1), (3,1,2) и (3,2,1).
Следовательно, строка является перестановкой другой строки, если она удовлетворяет следующим условиям:
- У обоих должны быть одинаковые персонажи.
- Оба должны иметь одинаковую длину.
- Пустая строка не считается. (не спрашивайте почему :))
Например, DOG, OGD, GOD и т. Д.
Здорово. Но этого мало. Что насчет…
Деликатный случай
Считаются ли буквы «G» и «g» одинаковыми или разными символами? Для меня все иначе. Но, может быть, у кого-то будет другое мнение.
Пустое пространство
Пробелы важны? Есть ли перестановки «аск» и «сак»? На мой взгляд, это не так, потому что длина явно различается, а один содержит «пустое пространство» в качестве символа. Но опять же, вы никогда не узнаете. Так что лучше убедиться, что здесь нет никакого подвоха.
В любом случае, для этой статьи, давайте решим, что это чувствительно к регистру и пробелы действительно важны t - иначе «Google» и «google» - не одно и то же, как и « Google »и« Google ».
Хорошо, теперь, когда у нас есть четкое представление об основных требованиях, мы можем перейти к следующим этапам - проанализировать ввод и разработать решение.
Анализируйте ввод
Во-первых, что такое правильный ввод?
Из нашего исследования, приведенного выше, ясно, что допустимыми входными данными будут допустимые строки, что означает не неопределенное, не нулевое или не пустое поле.
Если один из входов попадает в эти случаи, мы можем объявить проверку ложной.
Итак, какие возможные варианты входных данных мы можем захотеть протестировать?
Да, рекомендуется определить первые несколько случаев входных данных, на которых вы хотите запустить решение. Это не только поможет убедиться, что ваша логика охватывает все, что ей нужно, но и поможет дать более четкое направление к решению. Например:
- DOOG и DO G
- СОБАКА и СОБАКА
- ДОГО и ХОРОШО
- DOOG и GOOO
- gdoo и dGoo
- Конечно, не забывайте упомянутые выше недействительные случаи.
Когда мы закончили с примерами входных данных, перейдем к основной части - решению.
Решение
Из подготовленных выше мы уже разрабатываем первую часть решения - проверку действительности ввода. Помните, что одним из условий перестановки является то, что две входные строки должны иметь ТОЧНО одинаковую длину, поэтому у нас есть еще одна проверка действительности - проверка длины.
Итак, первая часть будет выглядеть примерно так
if strA not valid OR strB not valid OR strA.length !== strB.length
return false
Отлично, теперь мы можем с уверенностью предположить, что любой входной набор, прошедший этот тест, будет иметь одинаковую длину и действителен.
Из определения перестановки мы замечаем, что строки перестановки должны содержать точно такие же символы одинаковой длины, что означает, что количество вхождений каждого символа в одной строке должно совпадать с другим, в случае дублирования (скажем, DOOG и DOGO). Поскольку вхождение здесь имеет значение, мы не можем использовать помощь отдельного набора для сопоставления символов. Вместо этого мы можем:
- Сохраните объект сопоставления (хеш-таблицу) символов, появившихся в одной строке, с их вхождениями в этой строке. Затем мы можем проверить другую строку в объекте сопоставления - , которая представляет собой все символы другой строки, должны существовать в объекте сопоставления, и вхождения для каждого из них должны быть одинаковыми с тем, что сохранено на карте.
OR
- Отсортируйте обе строки с помощью эффективного алгоритма сортировки на месте, отсортированные строки должны быть идентичными, если они являются перестановками.
Замечательно, и… пришло время для настоящего кода (наконец-то)
Решение 1. Продолжайте отображать объект символов и их вхождений.
Обратите внимание, что при сравнении между map и strB, если символ действительно существует на карте с такими же вхождениями в B, каждое обнаруженное вхождение мы будем уменьшать вхождение, сохраненное в карте, на 1 , пока он не достигнет 0.
Любые отрицательные вхождения будут указывать на то, что этот символ не встречается в strB столько же времени, сколько в strA, что означает, что это не может быть перестановкой. Например: OO и OOO после сравнения будут иметь -1 число вхождений.
Решение 2 - Сортировка и сравнение.
Обратите внимание: мы использовали встроенный алгоритм сортировки для Array в JS - это означает, что мы конвертируем каждую строку в массив, сортируем ее и конвертируем обратно в строку. В конце все, что нам нужно сделать, это проверить идентичность преобразованных строк. Легкий кусок пирога!
Здесь вы можете реализовать другой метод сортировки, например написать собственный алгоритм mergeSort, quickSort и т. д.…. Неважно, что, если это эффективная сортировка на месте, она будет работать должным образом.
Теперь, когда мы закончили реализацию, можно задать последний вопрос.
Какое из них хорошее / лучшее?
Решение 1:
- У нас есть 2 основных цикла, каждый из которых занимает O (n) времени выполнения, где n - длина обоих strA и strB. Итого: O (n) + O (n) → O (n) линейное время работы.
- Однако нам действительно нужна помощь дополнительного объекта сопоставления t, которая может стоить нам до O (n) места в случае отсутствия дубликатов. во входных строках.
- Хорошая новость заключается в том, что максимальный размер этого объекта сопоставления составляет 128 (если это ASCII - у нас 128 символов) или 256 (если это расширенный ASCII), общее максимальное дополнительное пространство, которое у нас есть, не окажет существенного влияния на производительность, и это не пойдет дальше постоянного размера 128 или 256.
Решение 2:
- Сортировка займет примерно O (nlogn), если она реализована в MergeSort, и O (n) в среднем. случай, если это реализовано в QuickSort. Предположим, это O (nlogn).
- Каждое преобразование в массив и обратно займет O (n).
- Итого: O (nlogn) + O (n) + O (n) → O (nlogn) время работы
- Требуются два дополнительных массива одинакового размера с входами.
- Это очень четкое, короткое и легкое для понимания решение, но требует дополнительной сортировки и преобразования.
Как видите, у каждого есть свои плюсы и минусы. Оба, на самом деле, хорошие решения. Второе решение может показаться более простым и иногда предпочтительным, но когда дело доходит до эффективности, первое решение имеет тенденцию выигрывать.
Лично я предпочитаю не сортировать, если в этом нет крайней необходимости. И выполнение 3-х или 2-х петель на самом деле имеет значение. Зачем повторять цикл программы еще раз, когда в этом нет необходимости?
Итак, для меня 1-е решение, даже несмотря на то, что для этого требуется немного больше написания, в данном случае является более оптимальным выбором.
А ты? У вас есть другое решение / предпочтение? Если да, не стесняйтесь написать здесь. Я буду очень рад услышать ваше мнение, в конце концов, мы здесь, чтобы делиться друг с другом и учиться друг у друга, чтобы лучше писать код, не так ли :)?
Подведем итог еще раз: не забудьте запустить решение на примерах входных данных, которые мы определили ранее. Лучше будь осторожен, чем сожалеть! ;)
Большое спасибо за чтение и до встречи в следующей статье!
Если вам понравился этот пост и вы хотите узнать больше, ознакомьтесь с моими статьями.
Если вы хотите иногда меня догнать, подпишитесь на меня в Twitter | Facebook или просто посетите мой сайт портфолио.
