Учитывая строку S, как мы можем проверить, что погода мы можем преобразовать в палиндром или нет, просто изменив одну букву. Пожалуйста, помогите быстрому решению сделать это.Проверьте, можно ли сформировать палиндром
Пример: У нас есть S = "mixem". Тогда ответ ДА, поскольку мы можем изменить «e» на «i», чтобы сделать его палиндром.
Длина строки может составлять 1000 при макс.
Предполагая индексацию 0 на основе, достаточно проверить, для каждого 0 <= i < your_string_length, если число позиций, для которых символы в позициях i и your_string_length - i - 1 отличаются больше 2. Если да, то ответ также да, в противном случае это не.
В принципе, это проверяет, сколько пар символов с равным расстоянием от сторон строки различно: если только одна такая пара отличается, то мы можем изменить один из ее символов и сделать ее равной. Если больше пар, тогда нам нужно будет изменить больше символов.
Если я правильно понял ваш пример, это означает, что вы можете изменить одну букву на любую другую букву. Это делает алгоритм неловко простым. Вам нужно разобрать слово из сторон в центр и вычислить количество ошибок. Если это < = 1, то вы можете преобразовать в палиндром с 1 изменением или уже палиндром.
var s = "mixen", errors = 0;
for(var i = 0; i < s.length/2; i++){
if(s[i] != s[s.length-1-i]){
errors++;
}
var isPalindrom = errors == 0;
var isPalindromConvertible = errors <= 1;
PS. Вы не указали язык, поэтому я написал в наиболее удобном для меня сейчас: javascript
Где код, который вы пробовали? Вы пытались его реализовать. Не так ли? – nanndoj
@nanndoj Да, у меня есть. Но я хочу код, который может выполняться через половину секунды. Я попытался изменить каждую букву на противоположной стороне. Но это очень мало. – user3840069
Я не ваш нисходящий. Но это вопрос типа «сделай это для меня», который является сильным кандидатом на понижение. Я думаю, что лучший способ - предоставить свой код и обратиться за помощью в какой-то конкретный момент, который вы хотите улучшить! – nanndoj