CTCI Ch.1.2 Проверка перестановки

Привет и с праздником,

Мой вопрос касается задачи «1.2 Check Permutation» из «Cracking The Coding Interview», 6-е изд.

Когда мы сравниваем две строки, мы проверяем наличие в массиве любых значений, меньших 0. Это указывает на разное количество символов в наших двух строках. Однако разве сравнение не должно быть !== 0 вместо <0? Это позволит поймать как избыточные, так и недооцененные символы. Я не видел этого ни в книгах Errata, ни в каких-либо связанных результатах поиска.

Ниже приведено кодовое решение. (я в основном работаю на JS, поэтому возможно неправильно читаю код)

Спасибо заранее.

boolean permutation(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] letters = new int[128]; 

    char[] s_array = s.toCharArray();
    for (char c : s_array) {
            letters[c]++;
    }

    
    for (int i = 0; i < t.length(); i++) {
        int c = (int) t.charAt(i); 
        letters[c]--;
        if (letters[c] < 0) { // this is the line in question
            return false;
        }
    }
    return true;
}
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
0
165
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Самый первый тест для s.length() != t.length(). Как только код передал его, мы знаем, что имеется равное количество символов. Это означает, что если строки не являются перестановками, то есть символ, который чаще встречается в t, чем в s. Как только такой символ найден, мы заключаем, что t не является перестановкой.

Спасибо, но будет ли ранняя проверка работать, только если в какой-то момент мы удалим слишком много символов? Я не понимаю, как это могло бы покрыть случай, если бы длины строк были равны, но одна строка содержала больше символов определенного типа, чем другая строка. В этом случае нам также пришлось бы проверять, больше ли сумма 0. Я что-то пропустил? Другими словами, предоставленное решение проверяет, не вычли ли мы слишком много символов, но что, если мы вычли недостаточно?

Pmcorrea 26.12.2020 21:33

Я понимаю это сейчас. В случае, если мы удалим один из символов слишком много раз, частота уйдет в минус и сломается. Но если мы не удалили достаточно определенного символа, это должно означать, что либо был введен необычный символ в t, которого не будет на карте, и мы можем от него отказаться, либо, как вы сказали, будет введен общий символ, который появляется слишком часто в t и все равно приводит к отрицательному результату. Еще раз спасибо.

Pmcorrea 26.12.2020 23:18

Другие вопросы по теме