Привет и с праздником,
Мой вопрос касается задачи «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;
}
Сравнение для != 0
имеет смысл только после того, как будут вычислены все различия. Структура кода позволяет раннее обнаружение.
Самый первый тест для s.length() != t.length()
. Как только код передал его, мы знаем, что имеется равное количество символов. Это означает, что если строки не являются перестановками, то есть символ, который чаще встречается в t
, чем в s
. Как только такой символ найден, мы заключаем, что t
не является перестановкой.
Я понимаю это сейчас. В случае, если мы удалим один из символов слишком много раз, частота уйдет в минус и сломается. Но если мы не удалили достаточно определенного символа, это должно означать, что либо был введен необычный символ в t, которого не будет на карте, и мы можем от него отказаться, либо, как вы сказали, будет введен общий символ, который появляется слишком часто в t и все равно приводит к отрицательному результату. Еще раз спасибо.
Спасибо, но будет ли ранняя проверка работать, только если в какой-то момент мы удалим слишком много символов? Я не понимаю, как это могло бы покрыть случай, если бы длины строк были равны, но одна строка содержала больше символов определенного типа, чем другая строка. В этом случае нам также пришлось бы проверять, больше ли сумма 0. Я что-то пропустил? Другими словами, предоставленное решение проверяет, не вычли ли мы слишком много символов, но что, если мы вычли недостаточно?