Решение для проверки палиндрома С++ отключено одним тестовым случаем

Для заданной строки s проверьте, можно ли сделать из нее палиндром, удалив МАКСИМАЛЬНО один символ (это означает, что допускается удаление нуля). Строка s будет содержать ‹50 000 строчных букв алфавита.

Код, который я написал ниже, прошел 458/460 тестовых случаев и застрял на одном из них без видимой причины, возвращая false вместо true. Логика алгоритма проста, и я пробовал перемещать условные выражения, но, похоже, ничего не изменилось.

class Solution {
  public:
    bool ispalindrome; //holds result
    bool validPalindrome(string s) {
        bool candelete = true; //allows one delete
        ispalindrome = true; //initial condition
        int lcursor = 0;
        int rcursor = s.length() - 1;
        while(lcursor < rcursor && ispalindrome){
            //if cursor points at different letters
            if(s[lcursor] != s[rcursor]){
                // if delete is still allowed and delete works
                if(s[lcursor + 1] == s[rcursor] && candelete){
                    lcursor++;
                    candelete = false;
                } else if (s[lcursor] == s[rcursor - 1] && candelete){
                    rcursor--;
                    candelete = false;
                } else {
                    ispalindrome = false;
                }
            }
            lcursor++;
            rcursor--;
        }
        return ispalindrome;
    }
};

Тестовый пример, который отключает это решение, выглядит следующим образом:

aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga

Тестирование кода с помощью этого теста:

#include <iostream>
using std::string;

// class Solution { ... etc., from above

int main() {
  string s = "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga";
  std::cout << Solution().validPalindrome(s) << std::endl;
};

person William Su    schedule 30.05.2019    source источник
comment
Похоже, вам может понадобиться научиться использовать отладчик для пошагового выполнения кода. С хорошим отладчиком вы можете выполнять свою программу построчно и видеть, где она отклоняется от того, что вы ожидаете. Это важный инструмент, если вы собираетесь заниматься программированием. Дополнительная литература: Как отлаживать небольшие программы и Руководство по отладке   -  person NathanOliver    schedule 30.05.2019
comment
Вы знаете, что можете проверить наличие палиндрома в одной строке внутри одного оператора if, верно? stackoverflow.com/a/8362657/2104697   -  person Guillaume Racicot    schedule 30.05.2019
comment
это не палиндром: в слове есть лишняя буква, предпоследняя буква «у».   -  person Bianca    schedule 30.05.2019
comment
Двум последним комментаторам (@GuillaumeRacicot и @Bianca): вопрос заключается в том, можно ли сделать строку палиндромом, удалив букву.   -  person ShreevatsaR    schedule 30.05.2019
comment
Похоже, этот алгоритм всегда пытается удалить из первой половины списка, если совпадений нет. Я удивлен, что 458 из 560 тестов проходят успешно (или, может быть, я неправильно понимаю алгоритм). Я знаю, что в Stack Overflow есть много людей, которые настаивают на коде даже для вопросов по алгоритму, но IMO я бы предпочел, чтобы код, по крайней мере, сопровождался описанием на естественном языке, чтобы можно было отлаживать алгоритм вместо отладки кода. .   -  person ShreevatsaR    schedule 30.05.2019
comment
Где ваш отладочный след почему программа дает сбой? Вставить print команды, чтобы проиллюстрировать проблему, очень просто.   -  person Prune    schedule 31.05.2019
comment
@Prune Я не согласен. Программа терпит неудачу, возвращая false вместо true (как упоминалось в вопросе), потому что алгоритм ошибочен. Это не то, что вы можете обнаружить с операторами печати IMO.   -  person ShreevatsaR    schedule 31.05.2019
comment
@ShreevatsaR: простые операторы print показали бы недостаток алгоритма, который рассматривается как отсутствие проверки на наличие критического удаления.   -  person Prune    schedule 31.05.2019
comment
@Prune С 102-символьным тестовым примером (и, консервативно, в 2 раза больше операторов печати) читать операторы печати не легче, чем читать код. (В какой-то момент вы закончите тем, что просто проверите, что код делает то, для чего он написан.) Это та же проблема, что и попытка выполнить код с помощью отладчика: вам нужно знать, что вы ищете ( т. е. зная, что вместо этого должен был сделать алгоритм), что и является исходной проблемой.   -  person ShreevatsaR    schedule 31.05.2019
comment
У вас есть только несколько операторов print, хотя в тестовой строке будет 2-4 строки на символ. Задача не требует 102 символов; визуальный осмотр или банальный цикл покажет символ, который нужно удалить; тестовый пример может быть сокращен до не более 7 символов, что значительно снижает вывод. Поскольку OP знает алгоритм, который он реализовал, он якобы имеет представление о логических точках перегиба. И да, можно обнаружить это с помощью простых операторов print, как я знаю из отладки 50-100 тысяч строк трассировки, чтобы найти аномалии в следе сложного синтаксического анализатора.   -  person Prune    schedule 31.05.2019
comment
@Prune Я думаю, что вам не хватает того, что описанные вами части - это именно то, с чем просят о помощи - ОП знает свой алгоритм, но не знает, что не так с алгоритмом. Знание ее «логических точек перегиба» не помогает, когда исследуется сама эта логика. Если бы он мог применить минимизацию тестового примера и свести его к небольшому тестовому случаю, здесь не было бы вопроса (я сократил его до 5-символьного контрпримера, но только после того, как увидел ответ). Так как же, по-вашему, задавать такой вопрос, не будучи уже в состоянии ответить на него?   -  person ShreevatsaR    schedule 31.05.2019
comment
@ShreevatsaR Вам не нужно знать механизм сбоя, чтобы начать отслеживание. Во-первых, вы урезаете тестовый пример до меньшей структуры — сначала атакуйте эти точки перегиба на основе данных. Например, gulcupuculug удаляет 90 букв. Точки перегиба в коде очевидны: любая нелинейность в логическом потоке. Это предполагает 4-5 print утверждений. С 12 буквами это всего 60 строк вывода, и вы знаете, какая буква является триггером, так что вы можете посмотреть на место, которое имеет дело с lc слева, cul справа, и вручную проследить курсоры.   -  person Prune    schedule 31.05.2019
comment
Сокращение это до публикации, как я ожидаю, будет тестовым случаем из 5-7 символов и двух операторов печати. ОП мог или не мог заметить проблему и решение в этот момент. Тем не менее, я ожидаю, что плакат попытается свести к минимуму опубликованный пример в соответствии с рекомендациями SO.   -  person Prune    schedule 31.05.2019
comment
@Prune Спасибо, что нашли время объяснить. На мой взгляд, осознание того, что исходный 101-символьный тестовый пример можно уменьшить, удалив символы с каждого конца, а также внутри, является именно тем алгоритмическим пониманием, которое требует нескольких мгновений, чтобы убедить себя. ретроспективно, но часто отсутствует: в этом случае, как только кто-то доказывает себе, что такие символы не имеют значения, он не слишком далек от достижения действительно правильного (и оптимального, т.е. O (n)) алгоритма для проблемы. Итак, ИМО, это настоящая суть вопроса, и даже ответ просто указывает, что он может (1/2)   -  person ShreevatsaR    schedule 01.06.2019
comment
@Prune ... будь готов, это было бы полезно искреннему ученику. И ожидать, что это уже сделает человек, задающий вопрос, не кажется разумным, когда не хватает именно этого алгоритмического понимания (может быть, это слишком просто для вас, но не для всех — как я знаю из обучения простых алгоритмов студентам и видя, как их лица светятся) и просят о помощи. (Если бы это был вопрос, который в глубине души касался кода, а не алгоритма, я мог бы с вами согласиться.) Но я полагаю, что разумные люди могут не согласиться с этим, так что давайте остановимся здесь.   -  person ShreevatsaR    schedule 01.06.2019


Ответы (1)


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

Поэтому, если вы удаляете слева, вам также нужно проверить, возможно ли удаление справа, и (потенциально) проверить, нет ли палиндрома при удалении слева.

person 1201ProgramAlarm    schedule 30.05.2019
comment
else if (s[lcursor] == s[rcursor - 1] && candelete) не проверяет, можно ли удалить с правой стороны? - person NathanOliver; 30.05.2019
comment
@NathanOliver Это так, но если вы можете также удалить с левой стороны, он не вернется и проверит правую сторону, если удаление слева не образует палиндром. - person 1201ProgramAlarm; 30.05.2019
comment
Меньший тестовый пример, иллюстрирующий проблему: CUUCU. Алгоритм в вопросе удаляет начальное C как совпадение U, но вместо этого работает удаление конечного U. - person ShreevatsaR; 31.05.2019