首页 > 美团 8/29 笔试题 算法第三题解法(python)
头像
田园派程序猿
发布于 2021-08-29 12:56
+ 关注

美团 8/29 笔试题 算法第三题解法(python)

import sys
from collections import defaultdict
from bisect import bisect_left

s = sys.stdin.readline().strip()
a = sys.stdin.readline().strip()


def getIdx(s, a):
    ch2indices = defaultdict(list)
    for i, ch in enumerate(s):
        ch2indices[ch].append(i)

    for ch in a:
        if ch not in ch2indices:
            return -1

    indices = []
    continue_seq = ''
    ith = 0
    sidx = 0
    while ith < len(a):
        ch = a[ith]
        idx = bisect_left(ch2indices[ch], sidx)
        if idx != len(ch2indices[ch]):
            continue_seq += ch
            sidx = ch2indices[ch][idx] + 1
            ith += 1
        else:
            indices.append(sidx)
            continue_seq = ''
            sidx = 0

    if continue_seq:
        indices.append(sidx)
    total_idx = len(s) * (len(indices) - 1) + indices[-1] - len(a)
    return total_idx


print(getIdx(s, a))


全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐