Codeforces 1354B - Ternary Strin

日常一道算法题。

翻译

三元字符串

给你一个字符串，包含 1，2 或 3。你需要找到最短的包含 1 2 3 每个字符至少一次的字串。

可以删除开头和结束的任意数量的字符。

输入格式

输入整数 t 表示测试用例组数。

每个测试用例输入一行字符串 s。

可以保证所有测试用例的字符串的长度和不能超过 200000。

输出格式

每个测试用例输出一个整数，最小长度或 0。

分析

这是一道简单 dp 题，为了压缩空间，滚动计算 one，two，three 表示分别距离当前位置最近的 1，2，3的距离。

然后统计 result = min(result, max(one, two, three)) 注意最后输出的是 result + 1，而且要确认是否真的包含全部字符，特判 0 的情况。

代码(Python3)

# https://codeforces.com/problemset/problem/1354/B
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    string = input()
    one = -1
    two = -1
    three = -1
    result = len(string) + 1
    for index, c in enumerate(string):
        if c == '1':
            one = 0
        elif index > 0 and one >= 0:
            one = one + 1

        if c == '2':
            two = 0
        elif index > 0 and two >= 0:
            two = two + 1

        if c == '3':
            three = 0
        elif index > 0 and three >= 0:
            three = three + 1

        if one >= 0 and two >= 0 and three >= 0:
            result = min(result, max(one, two, three))
    
    if result == len(string) + 1:
        result = -1
        
    print(result + 1)

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.15 长春