Для заданной строки 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;
};
print
команды, чтобы проиллюстрировать проблему, очень просто. - person Prune   schedule 31.05.2019false
вместоtrue
(как упоминалось в вопросе), потому что алгоритм ошибочен. Это не то, что вы можете обнаружить с операторами печати IMO. - person ShreevatsaR   schedule 31.05.2019print
показали бы недостаток алгоритма, который рассматривается как отсутствие проверки на наличие критического удаления. - person Prune   schedule 31.05.2019print
, хотя в тестовой строке будет 2-4 строки на символ. Задача не требует 102 символов; визуальный осмотр или банальный цикл покажет символ, который нужно удалить; тестовый пример может быть сокращен до не более 7 символов, что значительно снижает вывод. Поскольку OP знает алгоритм, который он реализовал, он якобы имеет представление о логических точках перегиба. И да, можно обнаружить это с помощью простых операторовprint
, как я знаю из отладки 50-100 тысяч строк трассировки, чтобы найти аномалии в следе сложного синтаксического анализатора. - person Prune   schedule 31.05.2019gulcupuculug
удаляет 90 букв. Точки перегиба в коде очевидны: любая нелинейность в логическом потоке. Это предполагает 4-5print
утверждений. С 12 буквами это всего 60 строк вывода, и вы знаете, какая буква является триггером, так что вы можете посмотреть на место, которое имеет дело сlc
слева,cul
справа, и вручную проследить курсоры. - person Prune   schedule 31.05.2019