关键字标识

本文主要是介绍关键字标识，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个关键词集合 words 和一个字符串 inputStr，要求将 inputStr 中出现的所有关键词用标签标记：

关键词标签的起始为,结束为。
把可以合并的标签进行合并，即使用最少的标签。合并规则如下：
关键词相邻则进行合并，如 ab、cd为关键词，且在字符串中相邻，则合并为 abcd
关键词相交则进行合并，如 zhi、hid为关键词，且在字符串中相交，则合并为 zhid

解答要求

时间限制：1000ms, 内存限制：256MB

输入

第1行一个整数 count，表示 words 中的关键词的个数，取值范围：[1, 64]
第2行 count 个字符串，表示关键字词列表 words，每个关键词仅含英文小写字母，长度范围：[1,16]
第3行一个字符串 inputStr，仅含英文小写字母（无空格），长度范围：[1,512]

输出

一个用最少关键词标签标记的字符串

样例

输入样例 1

4
cd df op qr
opqracdfg

输出样例 1

<b>opqr</b>a<b>cdf</b>g

提示样例 1

关键词 op qr 出现在字符串中，且在字符串中相邻，因此可合并为 opqr；
cd df 出现在字符串中，且在字符串中相交，因此可合并为 cdf ；
其它字符保持不变。
处理后为 <b>opqr</b>a<b>cdf</b>g，使用了 2 个标签 。
<b>op</b><b>qr</b>a<b>cd</b><b>df</b>g也是一种标记方式，但关键词未作合并，需要用到 4 个标签，标签个数不是最少的。

输入样例 2

3
abbb def bbg
aabbbgz

输出样例 2

a<b>abbbg</b>z

提示样例 2

关键字abbb和bbg合并为abbbg

Java算法源码

import java.nio.charset.StandardCharsets;
import java.util.Scanner;
import java.util.HashSet;
import java.util.Scanner;public class Main {// 待实现函数，在此函数中填入答题代码private static String getTaggedString(String[] words, String inputStr) {HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));int[] result = setAllPos(wordSet, inputStr);if (result.length == 0) {return inputStr;}StringBuilder sb = new StringBuilder();for (int i = 0; i < result.length; i++) {if (result[i] == 1) {sb.append("<b>").append(inputStr.charAt(i)).append("</b>");} else {sb.append(inputStr.charAt(i));}}String convertStr = sb.toString();convertStr = convertStr.replace("</b><b>", "");return convertStr;}private static int[] setAllPos(HashSet<String> wordSet, String inputStr) {int len = inputStr.length();int[] result = new int[inputStr.length()];for (int i = 0; i < len; i++) {for (int j = i + 1; j <= len; j++) {if (wordSet.contains(inputStr.substring(i, j))) {for (int k = i; k < j; k++) {result[k] = 1;}}}}return result;}public static void main(String[] args) {Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());cin.nextLine();String[] words = cin.nextLine().split(" ");String inputStr = cin.nextLine();cin.close();String result = getTaggedString(words, inputStr);System.out.println(result);}
}

这篇关于关键字标识的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---