Задать вопрос
The_Dude_5463
@The_Dude_5463
Программист (Питон 3.5) - новичок

Как найти индекс лишнего символа, при удалении которого слово становится палиндромом?

В чём цель программы?
Программа должна вывести единственное число - номер буквы в строке, при удалении которой слово становится палиндромом. Если при удалении любой буквы слово не станет палиндромом, программа должна вывести число 0.

Сама задача звучит так:
Палиндромом называется слово, которое одинаково читается как слева направо, так и справа налево, например, в английском языке такими словами являются "radar" и "racecar".
Света изучает английский язык и решила принять участие в дистанционном конкурсе знатоков английского языка. Но, когда она писала ответ на задание "найдите самое длинное слово, которое является палиндромом", ошиблась и нажала на клавиатуре одну лишнюю клавишу. Определите, какую букву нужно удалить в набранном Светой слове, чтобы это слово стало палиндромом.
Программа получает на вход строку из строчных английских букв, содержащую не менее 2 и не более 100 000 символов.
5db1ffad2c950786407110.jpeg

Моя идея заключается в разделении слова пополам (отдельно для чётного и нечётного количества символов) и проверке попарно элементов (первого и последнего, второго и предпоследнего и т.д) до нахождения несоответствия. После этого индексы уникальной пары сохраняются. Проверяем первый символ пары с символом, идущим сразу за его парой (и то же самое для второго символа, если нужно). Если эти символы совпадают, то выводим индекс буквы, входящей в уникальную пару.

Идея корявая, с реализацией ещё хуже.
Буду благодарен любому дельному совету
  • Вопрос задан
  • 2650 просмотров
Подписаться 4 Средний 7 комментариев
Решения вопроса 1
The_Dude_5463
@The_Dude_5463 Автор вопроса
Программист (Питон 3.5) - новичок
Решение готово (по результатам сайта, который проверял его, оно прошло на 100 баллов из 100 возможных):

def f(c, i, j):
    while i < j:
        if c[i] != c[j]:
            return False
        i += 1
        j -= 1
    return True

c = str(input())
i = 0
j = len(c) - 1

if f(c, i, j):
    print(len(c) // 2 + 1)
    exit()
    
while i < j:
    if c[i] != c[j]:
        if f (c, i, j - 1):
            print(j + 1)
            exit()
        if f (c, i + 1, j):
            print (i + 1)
            exit()
        print('0')
        exit()
    i = i + 1
    j = j - 1
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
@MAGistr_MTM
Учусь программировать
Как по мне, то лучше пробегать по всему слову, и по-очереди удалять буквьі и проверять на палиндромность. Если слово палиндром - возвращать индекс той буквьі, если по оканчании прохода не бьіло ниединого палиндрома - вернуть 0
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Алгоритм (на вскидку, не проверял точность):
length - длина слова
idx - индекс символа слова от любого края по направлению к центру (1,2,3,...)
direction - направление отступа от центра слова (слева: -1; справа: +1)
half - половина длины слова с округлением в большую сторону (при нечётном количестве символов)

half=length+1>>1
direction=-1

1. проверяем слева
2. меняем знак направления отступа: direction*=-1
3. проверяем справа
4. инкрементируем отступ от краёв слова: idx++
5. idx<=half => GOTO 1
6. Позиция: half+direction*(half-idx)

Вариант 2 ("магический"):
1. Взять первую половину слова (через half-форомулу, что выше).
2. Развернуть всё слово и взять также его первую половину. Получим 2 части, которые должны быть равны, если это палиндром.
3. И.... вот, тут, магия: сделать XOR этим двум частям!
4. Первый единичный бит и будет искомая разница.
Ответ написан
coderisimo
@coderisimo
имхо, уот так уот :

def testAcronim(word):
  indx = 0 
  for i in word:
    test_string = word[:indx]+ word[indx+1:]
    if test_string==''.join(reversed(test_string)):
      print(indx)
      return
    indx +=1
  print(0)
Ответ написан
https://jsfiddle.net/or3a71w8/

let word = 'olololo';

function reverseString(str) {
    var splitString = str.split("");
    var reverseArray = splitString.reverse();
    var joinArray = reverseArray.join(""); 
    return joinArray; 
}
 
let reverseWord = reverseString(word);
let result = findIndex(word);

function findIndex(string) {
  if (!isPalindrom(string)) {
    for (let i = 0; i < word.length; i++) {
      let newWord = removeLetter(word, i, 1);
      if (isPalindrom(newWord)) {
       return i;
      }  
      return "C этого слова не сделаешь палиндром";
    }
  } else {
  	return "Это палиндром";
  }
}

function removeLetter(str, startIndex, count) {
    return str.substr(0, startIndex) + str.substr(startIndex + count);
}
function isPalindrom(string) {
	let reversedString = reverseString(string);
	return reversedString === string;
}

console.log(result);


Делал на скорую руку, этот код можно улучшить добавить проверки на колличество символов, делать проверку строка ли это вообще и т.д

p.s. только после написания ответа понял, что это нужно было сделать на питоне) Возможно мой пример на js,
как-то поможет)
Ответ написан
Комментировать
solotony
@solotony
покоряю пик Балмера
на счет "идеи": честно говоря я не совсем понял что ты хочешь сравнивать после нахождения первого расхождения.
1) идем до расхождения (середина - палиндром)
2) выкидываем слева - продолжаем до расхождения (середина - палиндром)
3) выкидываем справа - продолжаем до расхождения (середина - палиндром)
нет решения

def poly(s):
    L = len(s) - 1
    L2 = (L>>1) + 1
    print(s,L,L2)
    i=0
    while s[i]==s[L-i]:
        print('1:', i, s[i], s[L-i])
        i+=1
        if i==L2: return 0
    print('2:', i, s[i], s[L-i])
    k=i
    while s[k+1]==s[L-k]:
        print('3:', k, s[k+1], s[L-k])
        k+=1
        if k==L2: return i
    print('4:', k, s[k], s[L - k])
    k=i
    while s[k]==s[L-k-1]:
        print('5:', k, s[k], s[L-k-1])
        k+=1
        if k==L2: return L-i
    print('6:', k, s[k], s[L - k])
    return None
while True:
    s = input()
    print(s)
    print(poly(s))


qwertyytrewq
qwertyytrewq
qwertyytrewq 11 6
1: 0 q q
1: 1 w w
1: 2 e e
1: 3 r r
1: 4 t t
1: 5 y y
0
qwertyytrwq
qwertyytrwq
qwertyytrwq 10 6
1: 0 q q
1: 1 w w
2: 2 e r
3: 2 r r
3: 3 t t
3: 4 y y
3: 5 y y
2
qwrtyytrewq
qwrtyytrewq
qwrtyytrewq 10 6
1: 0 q q
1: 1 w w
2: 2 r e
4: 2 r e
5: 2 r r
5: 3 t t
5: 4 y y
5: 5 y y
8
qwertyytrewqww
qwertyytrewqww
qwertyytrewqww 13 7
2: 0 q w
3: 0 w w
4: 1 w w
6: 0 q w
None
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы