本题考查双指针与回文判定,需要在 O(n) 内找出所有“恰好删掉一个字符后成为回文”的下标。
从两端同时扫描,得到原串第一处失配位置 first_mis。删除下标 i 后,两端配对关系只在越过 i 时发生一次错位:
给定一个仅由小写英文字母组成的字符串 s,请判断它是否可以在删除一个字符之后,变成一个回文串。
回文串的定义是:从左到右读和从右到左读完全相同。
如果可以,输出一个数组,数组由可删除字符的索引值构成;否则输出一个空数组。
输入一个字符串 s,2≤s.length≤105
输出一个数组,内容为:N 种删除方法的字符索引值。如输入为:abca,则输出为:[1, 2],代表可以有两种删除方式:[aba, aca]。
1:删除索引值为 1 的字符,即删除字符 b,则变为:aca,属于回文2:删除索引值为 2 的字符,即删除字符 c,则变为:aba,属于回文输入
"abca"
输出
[1,2]
说明
删除 b 或删除 c 后,都可以变成回文串。
输入
"abcd"
输出
[]
说明
无论删除哪个字符,都无法变成回文串。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.