题目描述

给定一个字符串,问是否能通过添加一个字母将其变为回文串。

输入描述:

一行一个由小写字母构成的字符串,字符串长度小于等于10。

输出描述:

输出答案(YES\NO).

输入例子:

coco

输出例子:

YES

1 收藏


直接登录
最新评论
  • 超呆   06/13

    这么多天还没人来凑热闹么?我先扔块砖,来个最笨最慢的实现,大婶们请勿介意。

    此问题可分解为两步,添加一个字符,判断是否回文串

    添加字符部分又可以分为两种,原有字符串长度奇偶不同,添加规则也略有差异……

     

    开始偷懒吧,Javascritp最慢版

     

  • angelfish   06/14

    设当前处理的字符串数组为:a[i],a[i+1],…,a[j-1],a[j],其中0<=i<=j, 0<=j<n。

    判断a[i],a[i+1],…,a[j-1],a[j]添加一个字符能否变成回文串,分下面3种情况考虑:

    1、如果a[i] = a[j],则变成一个子问题:判断a[i+1],…,a[j-1]添加一个字符能否变成回文串。

    2、如果a[i] != a[j],判断a[i+1],…,a[j]是否是一个回文串。如果是的话,添加一个a[j+1],令a[j+1]=a[i],就能得到一个回文串。

    3、如果a[i] != a[j],判断a[i],…,a[j-1]是否是一个回文串。如果是的话,添加一个a[i-1],令a[i-1]=a[j],就能得到一个回文串。

     

    复杂度为:O(n)

  • arnoldxiao iOS渣渣 06/14

    • arnoldxiao iOS渣渣 06/15