Palindrome Index

HackerRank 問題: Palindrome Index
Categories:
Tags:

Question

HackerRank 問題: Palindrome Index

說明

字串 ccadaaaaaacc, d 是造成沒有 Palindrome 字串的字母

步驟 1，找出造成錯誤的前後字母 index

說明
字串 c c a d a a a a a a c c
索引 0 1 2 3 4 5 6 7 8 9 10 11
步驟 1 c c 比對相同
步驟 2 c c 比對相同
步驟 3 a a 比對相同
步驟 4 d a 比對不同

到 步驟 4，比對發生錯誤，所以造成錯誤的字串不是前面(d)，就是後面(a)

步驟 2，移除前方錯誤字串，檢查後方剩餘字串，確定是否為 Palindrome 字串

移除其中一個錯誤的字串，剩下的字串應該仍然為 Palindrome 字串

可能狀況有 2 個

  1. 移除 前面(d)，後面字串為 Palindrome 字串，則造成錯誤的字元是 前面(d)
  2. 移除 前面(d)，後面字串不為 Palindrome 字串，則造成錯誤的字元是 後面(a)
說明
字串 c c a d a a a a a a c c
索引 0 1 2 3 4 5 6 7 8 9 10 11
步驟 4 a a 比對相同
步驟 4 a a 比對相同
步驟 4 a 比對相同

後面比對的字串皆為相同，所以後面字串為 Palindrome 字串，造成錯誤字元一定是 前面(d)，所以 Palindrome 錯誤字串索引為 d 的索引位置 3

Answer

PHP

<?php

function palindromeIndex($check_string) {
    // initial checking index
    $total_length_of_string = strlen($check_string);
    $front_index = 0;
    $back_index = $total_length_of_string - 1;

    // find which index will cause non-palindrome
    while ($front_index < $back_index) {
        if ($check_string[$front_index] != $check_string[$back_index]) {
            // find letter not same, so one of letter will cause not palindrome
            break;
        }
        // find next letter
        $front_index++;
        $back_index--;
    }

    if ($front_index > $back_index) {
        // find the last letter, all the letter are same, so no palindrome index in the string
        return -1;
    }

    // split remain string from front index, check back string
    $remain_check_front_index = $front_index + 1;
    $remain_check_back_index = $back_index;

    // check remain back string is palindrome string
    while ($remain_check_front_index < $remain_check_back_index) {
        if ($check_string[$remain_check_front_index] != $check_string[$remain_check_back_index]) {
            // back letter is the index cause non-palindrome
            $palindrome_index = $back_index;
            return $palindrome_index;
        }
        $remain_check_front_index++;
        $remain_check_back_index--;
    }

    // remain back is palindrome, so front letter is the index cause non-palindrome
    $palindrome_index = $front_index;

    return $palindrome_index;
}

Python

def palindromeIndex(s):
    l = len(s)
    i = 0
    j = l-1
    while i<l:
        if s[i]!=s[j]:
            break
        i+=1
        j-=1
    if i>j: return -1
    a = i+1
    b = j
    while a<j and b>i+1:
        if s[a]!=s[b]:
            return j
        a+=1
        b-=1
    return i

for _ in range(int(input())):
    print(palindromeIndex(input()))

Reference