LeetCode 680. 验证回文字符串 Ⅱ

2020-05-19 16:08:30来源:博客园 阅读 ()

容器云强势上线!快速搭建集群,上万Linux镜像随意使用

LeetCode 680. 验证回文字符串 Ⅱ

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 680. 验证回文字符串 Ⅱ

题目

给定一个非空字符串?s,最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

  • 字符串只包含从 a-z 的小写字母。
  • 字符串的最大长度是50000。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-palindrome-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

至多删除一个,那么左右指针夹逼验证时有以下三种情况:

  • 无需删除;
  • 遇到了不等,删除左边的一个字符,继续验证;
  • 遇到了不等,删除右边的一个字符,继续验证;

三种情况除了初始指针位置区别外验证的模式相同;

思路1-记录指针的位置,提炼验证模式方法

最多需要进行三次模式验证,但是三次模式验证的指针起始位置需要记录;
指定两个变量记录指针的位置:

  • 首次验证若失败,则下面两个起始指针均为当前指针位置:
  • 左指针右移一步继续验证,若验证失败;
  • 右指针左移一步继续验证;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-递归验证

首次验证为递归的第一层,删除左或右一个字符为递归的第二层,所以递归需要严格控制只递归到第二层,设计使用一个boolean变量控制;
详见代码;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $ 栈的深度为2,常数级

思路3-直接在单个方法内一个while内解决

在首次验证失败时,需要验证左删除或者右删除,这里的思路是,先尝试左删除,若左删除验证失败,则在当前指针位置基础上让左指针向左回退一个位置,右指针前左进一个位置再继续验证,平衡掉先删左时多右移动的距离;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年5月19日 上午12:24:57 
 * @Description: 680. 验证回文字符串 Ⅱ
 *
 */
public class LeetCode_0680 {

}

class Solution_0680 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月19日 上午12:25:24 
	 * @param: @param s
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-两遍指针遍历,记录指针的位置,因为总共有三次机会去验证是否可改造成回文;
	 *
	 */
	private int start = 0;
	private int end = 0;

	public boolean validPalindrome_1(String s) {
		end = s.length() - 1;
		if (!check(s)) {
			int ss = start, ee = end;
			start++;
			if (!check(s)) {
				start = ss;
				end = ee;
				end--;
				return check(s);
			}
		}
		return true;
	}

	private boolean check(String s) {
		if (start > end) {
			return false;
		} else {
			while (start <= end) {
				if (s.charAt(start) == s.charAt(end)) {
					start++;
					end--;
				} else {
					return false;
				}
			}
			return true;
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月19日 上午12:52:52 
	 * @param: @param s
	 * @param: @return
	 * @return: boolean
	 * @Description: 2-递归验证,控制只递归两层;
	 *
	 */
	public boolean validPalindrome_2(String s) {
		return check(s, 0, s.length() - 1, true);
	}

	private boolean check(String s, int start, int end, boolean f) {
		while (start < end) {
			if (s.charAt(start) == s.charAt(end)) {
				start++;
				end--;
			} else {
				// 若是首次,则进行删除左或右再进行验证,否则说明无法改造为回文
				return f && (check(s, start + 1, end, false) || check(s, start, end - 1, false));
			}
		}
		return true;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月19日 上午1:09:12 
	 * @param: @param s
	 * @param: @return
	 * @return: boolean
	 * @Description: 3-单个方法内增加变量解决;
	 *
	 */
	public boolean validPalindrome_3(String s) {
		int left = 0, right = s.length() - 1;
		boolean leftDelete = true, rightDelete = true;
		while (left < right) {
			if (s.charAt(left) == s.charAt(right)) {
				left++;
				right--;
			} else {
				// 尝试删除左边
				if (leftDelete) {
					left++;
					leftDelete = false;
					// 尝试删除右边,此时左边要回退一个字符
				} else if (rightDelete) {
					left--;
					right--;
					rightDelete = false;
				} else {
					return false;
				}
			}
		}
		return true;
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12916339.html
如有疑问请与原作者联系

标签:AVIEClassPOSTHTTPSem

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:一个很艰难的 Java 核心面试问题!

下一篇:一个开发3年的程序员去跳槽,没想到面试却因这门技术挂了