刷题笔记合集🔗

问题描述

小兰在学习自然语言处理时，遇到了一个分词问题。给定一个不包含空格的字符串（仅包含小写字母和标点符号），需要根据给定的词库对其进行精确分词。

分词规则如下：

1. 精确分词：分词结果不能重叠，如"ilovechina"可以分为"i,love,china"或"ilove,china"，但不能分为"i,ilove,china"
2. 标点符号（逗号、分号、句号）只用于断句，不作为词
3. 分词时遵循"最长匹配"和"顺序优先"原则
4. 当字符无法匹配词库中的词时，按单个字符输出

输入格式

第一行输入待分词的字符串，长度范围(0, 256)。 第二行输入词库，词与词之间用英文标点符号分隔，词库长度范围(1, 100000)。

输出格式

输出分词结果，词之间用逗号分隔。

样例输入1

ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word

样例输出1

i,love,china

样例输入2

iat
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful

样例输出2

i,a,t

样例输入3

ilovechina,thewordisbeautiful
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful

样例输出3

i,love,china,the,word,is,beauti,ful

样例解释

1. 第一个样例中，按照最长匹配原则进行分词。
2. 第二个样例中，"a"和"t"不在词库中，按单个字符输出。
3. 第三个样例中，逗号用于断句，将句子分成两部分处理。

数据范围

• 字符串长度：(0, 256)
• 词库长度：(1, 100000)
• 字符串只包含小写字母和英文标点符号(,.;)
• 词库中的词只包含小写字母

中文分词模拟器

Python解法

import re

def cut_str(txt):
    """分割输入文本"""
    return re.split(r"[,.;]", txt)

def proc_text():
    # 初始化数据
    txt_lst = cut_str(input())
    wrd_set = set(cut_str(input()))
    res = []
    
    while txt_lst:
        # 获取当前文本
        cur = txt_lst.pop(0)
        idx = len(cur)
        
        while idx > 0:
            # 尝试匹配最长词
            part = cur[0:idx]
            
            if part in wrd_set:
                # 添加匹配词
                res.append(part)
                wrd_set.remove(part)
                
                # 处理剩余文本
                if idx < len(cur):
                    txt_lst.insert(0, cur[idx:])
                break
            
            idx -= 1
            
        # 处理未匹配情况
        if idx == 0:
            res.append(cur[0])
            if len(cur) > 1:
                txt_lst.insert(0, cur[1:])
    
    return ",".join(res)

print(proc_text())

Java解法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] txtArr = sc.nextLine().split("[,.;]");
        String[] wrdArr = sc.nextLine().split("[,.;]");
        System.out.println(procText(txtArr, wrdArr));
    }
    
    public static String procText(String[] txtArr, String[] wrdArr) {
        // 初始化数据结构
        HashSet<String> wrdSet = new HashSet<>(Array