网站建设后台有哪些项目,郑州网站建设三猫网络,网络规划设计师多少分,上海市招工网【问题描述】[第680题][验证回文字符串Ⅱ][简单]
给定一个非空字符串 s#xff0c;最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: aba
输出: True
示例 2:输入: abca
输出: True
解释: 你可以删除c字符。
注意:字符串只包含从 a-z 的小…【问题描述】[第680题][验证回文字符串Ⅱ][简单]
给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: aba
输出: True
示例 2:输入: abca
输出: True
解释: 你可以删除c字符。
注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。【解答思路】 考虑最朴素的方法首先判断原串是否是回文串如果是就返回 true如果不是则枚举每一个位置作为被删除的位置再判断剩下的字符串是否是回文串。这种做法的渐进时间复杂度是 O(n^2)的会超出时间限制。
首先考虑如果不允许删除字符如何判断一个字符串是否是回文串。常见的做法是使用双指针。定义左右指针初始时分别指向字符串的第一个字符和最后一个字符每次判断左右指针指向的字符是否相同如果不相同则不是回文串如果相同则将左右指针都往中间移动一位直到左右指针相遇则字符串是回文串。
在允许最多删除一个字符的情况下同样可以使用双指针通过贪心算法实现。初始化两个指针 low 和 high 分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同如果相同则更新指针令 low low 1 和 high high - 1然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同则两个字符中必须有一个被删除此时我们就分成两种情况即删除左指针对应的字符留下子串 s[low 1], s[low 1], …, s[high]或者删除右指针对应的字符留下子串 s[low], s[low 1], …, s[high - 1]。当这两个子串中至少有一个是回文串时就说明原始字符串删除一个字符之后就以成为回文串。
1. 贪心算法
时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public boolean validPalindrome(String s) {int low 0, high s.length() - 1;while (low high) {char c1 s.charAt(low), c2 s.charAt(high);if (c1 c2) {low;high--;} else {boolean flag1 true, flag2 true;for (int i low, j high - 1; i j; i, j--) {char c3 s.charAt(i), c4 s.charAt(j);if (c3 ! c4) {flag1 false;break;}}for (int i low 1, j high; i j; i, j--) {char c3 s.charAt(i), c4 s.charAt(j);if (c3 ! c4) {flag2 false;break;}}return flag1 || flag2;}}return true;}
}
2. 递归算法
时间复杂度O(N) 空间复杂度O(1) public boolean validPalindrome(String s) {int front 0;int end s.length() - 1;// 符号中间一个字符不影响回文与否while (front end) {if (s.charAt(front) ! s.charAt(end)) {return validPalindromeHelper(s, front 1, end) || validPalindromeHelper(s, front, end - 1);}front;end--;}return true;}public boolean validPalindromeHelper(String s, int front, int end) {while (front end) {if (s.charAt(front) ! s.charAt(end)) {return false;}front;end--;}return true;}【总结】
1. 数组题目
暴力思考优化考虑清楚边界 防止溢出多立flag递归解决
2. 判断回文串模板 public boolean validPalindromeHelper(String s, int front, int end) {while (front end) {if (s.charAt(front) ! s.charAt(end)) {return false;}front;end--;}return true;}
3.比较字符串中某些位置是否相等
**方法一Java charAt() 方法 // s.charAt(i) 每次都会检查数组下标越界 public char charAt(int index)
方法二转换成字符数组再用下标进行判断 char[] charArray s.toCharArray();转载链接https://leetcode-cn.com/problems/valid-palindrome-ii/solution/yan-zheng-hui-wen-zi-fu-chuan-ii-by-leetcode-solut/
