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