[LeetCode] 680. Valid Palindrome II

轉自LeetCode

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

<Solution>

125. Valid Palindrome 的衍生題

想法如下

• 一樣從頭尾檢查是否是 palindrome，如果發現不是，因為題目說可以刪除一個字元，所以會有兩種情況，假如位置 i 和位置 j 是不同字元

• 第一種情況，刪除位置 j 的字元，所以檢查 i, i+1 ... , j-1 是不是 palindrom

• 第二種情況，刪除位置 i 的字元，所以檢查 i+1, i+2 ... , j 是不是 palindrom

• 如果上述兩種情況都是 false，就直接回傳 false (因為題目說只能刪除一個字元，所以只要檢查一次不同的地方就可以了)

code 如下

Java

	class Solution {
	public boolean validPalindrome(String s) {
	final int upperBound = s.length() / 2;
	final int len = s.length();
	int end;
	for(int i = 0; i < upperBound; i++) {
	if(s.charAt(i) != s.charAt(len - 1 - i)) {
	end = len - 1 - i;
	return isValid(s, i, end-1) || isValid(s, i+1, end);
	}
	}
	return true;
	}
	private boolean isValid(String s, int start, int end) {
	while(start <= end) {
	if(s.charAt(start++) != s.charAt(end--)) {
	return false;
	}
	}
	return true;
	}
	}

view raw validPalindrome.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun validPalindrome(s: String): Boolean {
	val upperBound = s.length / 2
	for(i in 0 until upperBound) {
	val end = s.lastIndex-i
	if (s[i] != s[end]) {
	return isValid(s, i+1, end) || isValid(s, i, end-1)
	}
	}
	return true
	}
	private fun isValid(s: String, start: Int, end: Int): Boolean {
	var startIndex = start
	var endIndex = end
	while(startIndex < endIndex) {
	if (s[startIndex++] != s[endIndex--]) {
	return false
	}
	}
	return true
	}
	}

view raw valid_palindrome_II.kt hosted with ❤ by GitHub