【牛客網華為機試】HJ32 密碼截取

題目

描述

Catcher是MCA國的情報員，他工作時發現敵國會用一些對稱的密碼進行通信，比如像這些ABBA，ABA，A，123321，但是他們有時會在開始或結束時加入一些無關的字元以防止别國破解。比如進行下列變化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因為截獲的串太長了，而且存在多種可能的情況（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量實在是太大了，他隻能向電腦高手求助，你能幫Catcher找出最長的有效密碼串嗎？

本題含有多組樣例輸入。

輸入描述：

輸入一個字元串

輸出描述：

傳回有效密碼串的最大長度

示例1

輸入：

ABBA
           

輸出：

4
           

解題思路

（1）按題目要求即找到從中間位置開始往左右兩邊擴充能保持對稱的最大字元串長度

（2）字元串長度為偶數時，對稱中線左右兩邊的字元相等，即

string[i] == string[i+1]
           

（3）字元串長度為奇數時，對稱中心字元左右兩邊的字元相等，即

string[i-1] == string[i+1]
           

（4）從中心點index出發，向兩邊尋找，元素相等則最大長度+2，否則輸出目前最大長度

代碼

def max_len(string):
    abba = []
    aba = []
    #周遊尋找對稱位置
    for i in range(len(string)-1):
        current = i
        next_one = i+1
        if string[current] == string[next_one]:
            abba.append(i)
        elif string[current-1] == string[next_one]:
            aba.append(i)
    length = []
    for j in abba:
        first = j
        last = j+1
        while first>=0 and last<len(string) and string[first]==string[last]:
            first+=-1
            last+=1
            #CABBA，第一循環時，符合條件的隻有2個字元，而此時last-first=3,是以需要減去1
            length.append(last-first-1)
    for k in aba:
        first = k-1
        last = k+1
        while first>=0 and last<len(string) and string[first] == string[last]:
            first+=-1
            last +=1
            length.append(last-first-1)
    if len(length)==0:
        return 0
    else:
        return max(length)

while True:
    try:
        string = input()
        print(max_len(string))
    except:
        break
                
            
           

Reference

https://www.nowcoder.com/ta/huawei/