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
}

參考資料