BAEKJOON#17609文(文字列)-python

回文
ソース:白駿#17609
タイムアウトメモリ制限1秒512 MB
質問する
回文または回文とは、前後方向の同じ順序の文字からなる文字列を指す.例えば「abba」「kayak」「revier」「奥さん」はすべて返事です.それ自体が回文ではないが、文字を削除して回文にする文字列であれば、この文字列を「偽回文」(pseudo palindrome)と呼ぶ.例えば、「summus」は5文字目または6文字目「u」を除いて「summus」の返信となるため、類似の返信となる.
提案した文字列を分析し、それ自体が回文なのか、文字を削除して回文の「類詞回文」になったのか、回文や類詞回文の普通の文字列ではないのかを判断します.文字列自体が回文の場合は0を出力し、同様の回文の場合は1を出力し、他の出力は2を出力する.
入力
入力された最初の行は、与えられた文字列の個数を表す整数T(1≦T≦30)を与える.次の行から、T行の各行に文字列を入力します.与えられた文字列の長さは3以上100000以下であり、英字小文字のみからなる.
しゅつりょく
各文字列が返信文であるか類似返信文であるかを判断し、両文字列とも対応せず、返信文が0、類似返信文が1、2または2の順に出力する.
I/O例
入力例1
7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc
サンプル出力1
0
1
1
2
2
0
1
に答える
思考と解答説明

は、最初に2つのポインタで近づこうとした.

元の文字列リストの逆順リストが異なる場合(回文でなければ)、start=0、end=n-1として残り、両側から1マス減らして誤った部分を探索する.

、該当する部分が見つかった場合、

1)まずstart+=1の場合(先頭の要素を除く)を考慮し,両側とも同様に1格縮小し,誤った部分を探索する.

2)もう一度エラーが発生すれば「類似回文」の可能性はないので,end-=1により最後の要素以外の探索を行った.

3)どちらもやってしまって、間違ったところがもう一度出てきたら、「似たような返事」の可能性がないので、2を返しました.

この方法では、次の反例を使用できません.

abcddcdba

理由は1)の誤り部分が探索されるからである.(無効な要素を削除...)

実際には、cddcdでは最初の要素を排除すべきではなく、最後の要素を排除すべきであるが、順序記述されたコードが1)のエラー部分が検出されると、2が返される.

# 백준 17609번 회문 (틀린 코드)
def solution(string, count):
    n = len(string)
    r_string = list(reversed(string))
    if string == r_string:
        return 0
    else:
        if count < 1:
            start = 0
            end = n-1
            while start < end:
                if string[start] == string[end]:
                    start += 1
                    end -= 1
                else:
                    count += 1
                    if string[start+1] == string[end]:
                       start += 1
                    elif string[start] == string[end-1]:
                       end -= 1
                    else:
                        return 2
                    if count > 2:
                        return 2
        else:
            return 1

次のコードは、上記の問題を解決するコードです.

まず、最初の文字列が返信時のcountではないことを確認します.

countが2(0 or 1)未満の場合、ポインタstart、endを使用してナビゲートします.

探索中にエラーに遭遇した場合(上の方法とは違う!!)、左端要素の削除と右端要素の削除を求める.

復帰の戻り値がゼロの場合は「類似回文」となりますので1を返します.その他の場合は「類似回文」でもないので2を返します.

python code

# 백준 17609번 회문
from sys import stdin
input = stdin.readline

def solution(string, count):
    n = len(string)
    r_string = list(reversed(string))
    if string == r_string:
        return 0
    else:
        if count < 1:
            start = 0
            end = n-1
            while start < end:
                if string[start] == string[end]:
                    start += 1
                    end -= 1
                else:
                    count += 1
                    a = solution(string[start+1:end+1], count)  # 왼쪽 원소 하나 제외
                    b = solution(string[start:end], count)      # 오른쪽 원소 하나 제외
                    if min(a, b) == 0:
                        return 1
                    else:
                        return 2
        else:
            return 2    # 두 개 이상 원소 제외의 경우
                    


t = int(input())
answer = []
for i in range(t):
    string = list(map(str, input().rstrip()))
    result = solution(string, 0)
    answer.append(result)

for j in range(t):
    print(answer[j])