阿里2019算法第一题算法

# @date: 2018/9/7 19:53
# @author: wangke
# @concat: wangkebb@163.com
# =========================

"""
输入:
输入数据包含两行，
第一行，实体列表，多种实体之间用分号隔开，实体名和实体值之间用下划线隔开，多个实体值之间用竖线隔开，所有标点都是英文状态下的，格式如下：
实体名称1_实体值1|实体值2|…;实体名称2_实体值1|实体值2|…;…
第二行，用户的自然语言指令

输出:
被标记了关键词的指令。指令中的关键词前后加一个空格被单独分出来，并在后面跟上"/"+实体名称来标记。
如果一个实体值属于多个实体，将这些实体都标记出来，并按照实体名称的字符串顺序正序排列，并以逗号分隔。


输入范例:
singer_周杰|周杰伦|刘德华|王力宏;song_冰雨|北京欢迎你|七里香;actor_周杰伦|孙俪
请播放周杰伦的七里香给我听
请播放 周杰伦 的七里香给我听
start:i


输出范例:
请播放 周杰伦/actor,singer 的 七里香/song 给我听
"""


def format_pattern(s):
    pattern = {}
    for i in s.split(";"):
        attr, names = i.split("_")
        names = names.split("|")
        for name in names:
            if name in pattern:
                pattern[name] += ",%s" % attr
            else:
                pattern[name] = attr

    return pattern


def match(content, pattern):
    max_char_len = max(map(len, pattern.keys()))

    start = 0
    latest_index = 0
    results = []
    for i in range(len(content)):
        for j in range(max_char_len - 1, -1, -1):
            temp = content[start:i + j]
            if temp in pattern:
                upper = content[latest_index:start]
                results += [upper, temp]
                latest_index = start + len(temp)
                break

        # 遍历完成
        start += 1

    # 最后一个
    results.append(content[latest_index:len(content)])

    results = ["%s/%s" % (k, pattern[k]) if k in pattern else k for k in results]
    print(" ".join(results))


def main():
    input1 = "singer_周杰|周杰伦|刘德华|王力宏;song_冰雨|北京欢迎你|七里香;actor_周杰伦|孙俪"
    input2 = "请播放周杰伦的七里香给我听, 不是刘德华的冰雨"
    # input2 = "请播放周杰伦的七里香给我听"

    pattern = format_pattern(input1)

    match(input2, pattern)


if __name__ == '__main__':
    main()

image.png

伤心了...