Является ли одна строка перестановкой другой?

Определить, является ли одна строка перестановкой другой

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

Способ 1. Сортировка

Если одна строка является перестановкой другой, очевидно строки должны состоять из одних и тех же символов, но в разном порядке. Тогда после сортировки строки должны совпадать.

Достоинство этого метода — простота и наглядность, однако для больших строк он не эффективен. Сортировка, как ни крути, имеет сложность n*log(n) .

Если требуется решить за линейное время — есть способ лучше.

Способ 2. Счетчики символов

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

Очевидно, что второй способ быстрее первого, однако для строк размером меньше миллиона символов разницы практически нет.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.