680. Valid Palindrome II

Leetcode 问题: 680. Valid Palindrome II
Categories:
Tags:

题目

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

是否可以 最多移除一字元 变成 Palindrome 字串

演算法

1. 从左右指标开始检查是否为 Palindrome 字串

如果整个字串是 Palindrome 字串，那从一开始的左右指标检查到的字母椰应该相同，符合 Palindrome 字串定义

2. 遇到不是 Palindrome 字母时，检查左右子字串

当有检查到一个字母前后比对，导致不是 Palindrome 字串时，依照题目定义，有可能是左指标的字母错误，也有可能是 右指标的字母错误

所以分别包含现有的左右指标文字，分别检查左右各半边的字串是否为 Palindrome 字串

  • 左侧：[ leftPointer, rightPointer -1 ]，不看右侧指标字母
  • 右侧：[ leftPointer + 1, rightPointer ]，不看左侧指标子母

如果当其中之一是 Palindrome 字串，那表示可以删除一个字母，让整个字串变成 Palindrome 字串

答案

JavaScript

function validPalindrome(checkText) {
    // 设定检查指标
    var leftPointer = 0;
    var rightPointer = checkText.length - 1;
    while (leftPointer <= rightPointer) {
        // 取得指标字母
        var leftLetter = checkText[leftPointer];
        var rightLetter = checkText[rightPointer];
        if (leftLetter != rightLetter) {
            // 假如左右子母不相同，移除前后一个字，检查是否为 Palindrome 字串
            return (isPalindromeText(checkText, leftPointer, rightPointer - 1)
                || isPalindromeText(checkText, leftPointer + 1, rightPointer));
        }
        // 移动下一个检查指标
        leftPointer++;
        rightPointer--;
    }
    return true;
}

// 检查是否为 Palindrome 字串
function isPalindromeText(checkText, leftPointer, rightPointer) {
    while (leftPointer < rightPointer) {
        // 取得指标字母
        var leftLetter = checkText[leftPointer];
        var rightLetter = checkText[rightPointer];
        if (leftLetter != rightLetter) {
            // 字母检查不同，不是 Palindrome 字串
            return false;
        }
        // 移动下一个检查指标
        leftPointer++;
        rightPointer--;
    }
    // 字母都相同，为 Palindrome 字串
    return true;
}

TypeScript

function validPalindrome(checkText: string): boolean {
    // 设定检查指标
    let leftPointer = 0;
    let rightPointer = checkText.length - 1;

    while (leftPointer <= rightPointer) {
        // 取得指标字母
        let leftLetter = checkText[leftPointer];
        let rightLetter = checkText[rightPointer];

        if (leftLetter != rightLetter) {
            // 假如左右子母不相同，移除前后一个字，检查是否为 Palindrome 字串
            return (isPalindromeText(checkText, leftPointer, rightPointer -1)
                || isPalindromeText(checkText, leftPointer + 1, rightPointer));
        }
        // 移动下一个检查指标
        leftPointer++;
        rightPointer--;
    }
    return true;
};

// 检查是否为 Palindrome 字串
function isPalindromeText(checkText: string, leftPointer: number, rightPointer: number) {
    while (leftPointer < rightPointer) {
        // 取得指标字母
        let leftLetter = checkText[leftPointer];
        let rightLetter = checkText[rightPointer];
        if (leftLetter != rightLetter) {
            // 字母检查不同，不是 Palindrome 字串
            return false;
        }
        // 移动下一个检查指标
        leftPointer++;
        rightPointer--;
    }

    // 字母都相同，为 Palindrome 字串
    return true;
}

Golang

// 是否移除一字元变成反转母音字
func validPalindrome(checkText string) bool {
	// 将检查的文字转换成 byte (uint8)
	checkTextByte := []byte(checkText)
	// 设定检查索引
	frontLetterIndex := 0
	backLetterIndex := len(checkTextByte) - 1

	for frontLetterIndex < backLetterIndex {

		// 检查字母是否相同
		if checkTextByte[frontLetterIndex] != checkTextByte[backLetterIndex] {
			// 若字母不相同，去除前后个一个字，检查是否为 Palindrome 文字
			return isPalindromeText(checkTextByte, frontLetterIndex, backLetterIndex-1) || isPalindromeText(checkTextByte, frontLetterIndex+1, backLetterIndex)
		}

		// 字母相同，移动前后字母索引
		frontLetterIndex++
		backLetterIndex--
	}

	// 字母都相同，为 Palindrome 文字
	return true
}

// 检查是否为 Palindrome 文字
func isPalindromeText(checkTextByte []byte, frontLetterIndex int, backLetterIndex int) bool {
	for frontLetterIndex < backLetterIndex {
		if checkTextByte[frontLetterIndex] != checkTextByte[backLetterIndex] {
			// 若字母不相同，则不是 Palindrome 文字
			return false
		}

		// 字母相同，移动前后字母索引
		frontLetterIndex++
		backLetterIndex--
	}

	// 字母都相同，为 Palindrome 文字
	return true
}

完整程式码

package main

import (
	"fmt"
)

type Question struct {
	// 参数
	Parameter
	// 答案
	Answer
}

// 参数
type Parameter struct {
	checkText string
}

// 答案
type Answer struct {
	result bool
}

func main() {

	QuestionList := []Question{
		{
			Parameter{"abca"},
			Answer{true},
		},
		{
			Parameter{"aba"},
			Answer{true},
		},
		{
			Parameter{"abc"},
			Answer{false},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 680------------------------\n")
	for _, question := range QuestionList {
		param := question.Parameter
		expectAnswer := question.Answer
		exactAnswer := validPalindrome(param.checkText)
		fmt.Printf("【input】:%v       【output】:%v     【expect】:%v\n", param, exactAnswer, expectAnswer.result)
	}
}

// 是否移除一字元变成反转母音字
func validPalindrome(checkText string) bool {
	// 将检查的文字转换成 byte (uint8)
	checkTextByte := []byte(checkText)
	// 设定检查索引
	frontLetterIndex := 0
	backLetterIndex := len(checkTextByte) - 1

	for frontLetterIndex < backLetterIndex {

		// 检查字母是否相同
		if checkTextByte[frontLetterIndex] != checkTextByte[backLetterIndex] {
			// 若字母不相同，去除前后个一个字，检查是否为 Palindrome 文字
			return isPalindromeText(checkTextByte, frontLetterIndex, backLetterIndex-1) || isPalindromeText(checkTextByte, frontLetterIndex+1, backLetterIndex)
		}

		// 字母相同，移动前后字母索引
		frontLetterIndex++
		backLetterIndex--
	}

	// 字母都相同，为 Palindrome 文字
	return true
}

// 检查是否为 Palindrome 文字
func isPalindromeText(checkTextByte []byte, frontLetterIndex int, backLetterIndex int) bool {
	for frontLetterIndex < backLetterIndex {
		if checkTextByte[frontLetterIndex] != checkTextByte[backLetterIndex] {
			// 若字母不相同，则不是 Palindrome 文字
			return false
		}

		// 字母相同，移动前后字母索引
		frontLetterIndex++
		backLetterIndex--
	}

	// 字母都相同，为 Palindrome 文字
	return true
}

参考资料