
问题
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
输入: “aba”
输出: True
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Input: “aba”
Output: True
Input: “abca”
Output: True
Explanation: You could delete the character ‘c’.
Note:The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
示例
public class Program { public static void Main(string[] args) { var s = "abca"; var res = ValidPalindrome(s); Console.WriteLine(res); s = "Iori's Blog!"; res = ValidPalindrome2(s); Console.WriteLine(res); Console.ReadKey(); } private static bool ValidPalindrome(string s) { //暴力解法,超时未AC if(IsPalindrome(s)) return true; for(int i = 0; i < s.Length; i++) { var substring = s.Remove(i, 1); if(IsPalindrome(substring)) return true; } return false; } private static bool IsPalindrome(string s) { //前后双指针法 var i = 0; var j = s.Length - 1; while(i < j) { if(s[i] != s[j]) return false; i++; j--; } return true; } public static bool ValidPalindrome2(String s) { var i = -1; var j = s.Length; while(++i < --j) //不相同时,并不代表就不是回文了,因为有删除一个字符的机会 //但我们不知道往前删除还是往后删除 //所以我们前后各判定一次 if(s[i] != s[j]) return IsPalindrome2(s, i, j - 1) || IsPalindrome2(s, i + 1, j); return true; } private static bool IsPalindrome2(String s, int i, int j) { while(i < j) if(s[i++] != s[j--]) return false; return true; } }
以上给出2种算法实现,以下是这个案例的输出结果:
True False
分析:
显而易见,ValidPalindrome 的时间复杂度为: ,ValidPalindrome2 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3961。