中文分词模拟器 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

给定一个连续不包含空格字符的字符串，该字符串仅包含英文小写字母及英文标点符号（逗号、句号、分号），同时给定词库，对该字符串进行精确分词。

说明：

• 精确分词：字符串分词后，不会出现重叠。例如 "ilovechina"，不同切分后可得到 "i", "love", "china"。

• 标点符号不分词，仅用于断句。

• 词库：根据常识及词库统计出来的常用词汇。例如：dictionary={"i","love","china","ilovechina","lovechina"}。

• 分词原则:采用分词顺序优先且最长匹配原则。“ilovechina”，假设分词结果[i,ilove,lo,love,ch,china,lovechina] 则输出 [ilove,china]

  • 错误输出：[i, lovechina]，原因："ilove" > 优先于 "lovechina" 成词。

  • 错误输出：[i, love, china]，原因："ilove" > "i"，遵循最长匹配原则。

输入描述

1. 字符串长度限制：0 < length < 256
2. 词库长度限制：0 < length < 100000
3. 第一行输入待分词语句 "ilovechina"
4. 第二行输入中文词库 "i, love, china, ch, na, ve, lo, this, is, the, word"

输出描述

按顺序输出分词结果 "i, love, china"

示例1

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

输出：
i,love,china

说明：
输入的字符串被按最长匹配原则分为 "i", "love", "china"。

示例2

输入：
ilovech
i,love,china,ch,na,ve,lo,this,is,the,word

输出：
i,love,ch

说明：
输入的字符串被按最长匹配原则分为 "i", "love", "ch"。

题解

这道题目属于字符串处理和字典树（Trie）应用的题目。题解思路如下：

1. 构建字典树（Trie）：
   • 使用字典树来存储词库中的单词，方便高效地进行查找和匹配。
2. 分词过程：
   • 对输入的字符串进行遍历，从当前位置向后进行匹配。
   • 尽量匹配最长的单词，如果匹配成功，则将该单词加入结果列表。
   • 如果没有匹配到词库中的任何单词，则将当前字符作为一个单词加入结果列表。
3. 时间复杂度：
   • 构建字典树的时间复杂度是 O(n)，其中 n 为词库中所有单词的总长度。
   • 分词的时间复杂度是 O(m)，其中 m 为待分词字符串的长度。
4. 空间复杂度：
   • 字典树的空间复杂度是 O(n)，其中 n 为词库中所有单词的总长度。

Java

import java.util.*;
/**
 * @author code5bug
 */
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEndOfWord = true;
    }

    public List<String> searchAll(String text) {
        List<String> result = new ArrayList<>();
        int length = text.length();
        for (int i = 0; i < length; ) {
            TrieNode node = root;
            int longestMatch = -1;
            for (int j = i; j < length; j++) {
                char ch = text.charAt(j);
                if (!node.children.containsKey(ch)) {
                    break;
                }
                node = node.children.get(ch);
                if (node.isEndOfWord) {
                    longestMatch = j;
                }
            }
            if (longestMatch == -1) {
                result.add(text.substring(i, i + 1));
                i++;
            } else {
                result.add(text.substring(i, longestMatch + 1));
                i = longestMatch + 1;
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String text = scanner.nextLine().trim();
        String[] dictionaryWords = scanner.nextLi