题目描述
小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。
新词挖掘：给出一个待挖掘问题内容字符串Content和一个词的字符串word，找到content中所有word的新词。
新词：使用词word的字符排列形成的字符串。
请帮小华实现新词挖掘，返回发现的新词的数量。
输入描述
第一行输入为待挖掘的文本内容content；
第二行输入为词word；
输出描述
在content中找到的所有word的新词的数量。
备注
- 0 ≤ content的长度 ≤ 10000000
- 1 ≤ word的长度 ≤ 2000
用例
| 输入 | qweebaewqd qwe |
| 输出 | 2 |
| 说明 |
起始索引等于0的子串是“qwe”，它是word的新词。 起始索引等于6的子串是“ewq”，它是word的新词。 |
| 输入 | abab ab |
| 输出 | 3 |
| 说明 |
起始索引等于0的子串是”ab“，它是word的新词。 起始索引等于1的子串是”ba“，它是word的新词。 起始索引等于2的子串是”ab“，它是word的新词。 |
暴力解法（可得100%通过率）
本题最简单的解法就是利用定长（word长度）滑动窗口来选择 content中的子串，只要选中的子串和word二者，在字典序排序后是一样的，则可以记为一个挖掘到的新词。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const content = lines[0];
const word = lines[1];
console.log(getResult(content, word));
lines.length = 0;
}
});
function getResult(content, word) {
if (content.length < word.length) {
return 0;
}
const sorted_word = [...word].sort().join("");
let ans = 0;
let maxI = content.length - word.length;
for (let i = 0; i <= maxI; i++) {
const sorted_substr = [...content.slice(i, i + word.length)]
.sort()
.join("");
if (sorted_substr === sorted_word) ans++;
}
return ans;
}
Java算法源码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String content = sc.next();
String word = sc.next();
System.out.println(getResult(content, word));
}
public static int getResult(String content, String word) {
if (content.length() < word.length()) return 0;
char[] tmp = word.toCharArray();
Arrays.sort(tmp);
String sorted_word = new String(tmp);
int ans = 0;
int maxI = content.length() - word.length();
int len = word.length();
for (int i = 0; i <= maxI; i++) {
char[] window = content.substring(i, i + len).toCharArray();
Arrays.sort(window);
if (sorted_word.equals(new String(window))) {
ans++;
}
}
return ans;
}
}
Python算法源码
# 输入获取
content = input()
word = input()
# 算法入口
def getResult(content, word):
# 如果content长度小于word，则直接返回0
if len(content) < len(word):
return 0
sorted_word = "".join(sorted(list(word)))
ans = 0
maxI = len(content) - len(word)
for i in range(maxI + 1):
sorted_subStr = "".join(sorted(content[i:i + len(word)]))
if sorted_subStr == sorted_word:
ans += 1
return ans
# 算法调用
print(getResult(content, word))
优化解法
上面暴力解法的时间复杂度在：O(n*m)，其中n是content长度，m是word长度，也就是说，最多的会有10000000 * 2000次循环，有人可能会疑问时间复杂度中m哪来的？那是content截取出来的子串字典序排序的时间复杂度m。
因此上面的算法极其容易超时。
那么上面算法是否有优化的可能呢?
我的优化思路是，利用word和content截取子串的字母数量 比较 来代替 字典序排序后比较。
因为字典序排序存在一个较大的性能浪费，比如
qweebaewqd
xyz
我们可以明显发现，content中不存在word新词，因为任意位置长度3的滑动窗口中的第一个字母都不属于word，因此仅从滑动窗口内第一个字母就可以判断出结果，而不是需要截取子串字典序排序后再比较得出结果。
但是，通过字母数量比较也有缺陷，那就是，如果只有滑动窗口内部各字母数量和word的字母数量严格一致，才能算挖掘到了新词。
我的实现思路是：
遍历滑动窗口内部的字母，如c，如果该字母c是word中的，则先看统计数量count[c]是不是已经为0了，如果已经为0了，则说明当前滑动窗口遍历到的字母c是超标部分，因此当前滑动窗口不可用。下一个滑动窗口应该保证字母c不超标，即下一个滑动窗口的左边界应该在当前滑动窗口中字母c第一次出现位置的右边。
当然，如果遍历完滑动窗口内部所有字母，也没有出现超标现象，则说明该滑动窗口就是要挖掘的新词。
上面算法逻辑，其实我不太确定是否有多大的性能提升，但是相较于字典序排序应该有较多提升。我把上面算法逻辑称为跳跃式，即滑动窗口的左边界不是单纯一格一格往右滑的，而是可以多格滑动的。
为了以防万一，我这里还想了一个传统滑动窗口的解法，那就是一格一格移动，但是也是通过统计滑动窗口内部字母数量来判断是否是word新词，但是后一个滑动窗口可以通过差异化思想，快速基于前一个滑动窗口得出自身内部字母数量。这块逻辑可以参考：
中求解最小覆盖子串的过程。
JavaScript算法源码
跳跃式
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const content = lines[0];
const word = lines[1];
console.log(getResult(content, word));
lines.length = 0;
}
});
function getResult(content, word) {
// 如果content长度小于word，则直接返回0
if (content.length < word.length) {
return 0;
}
// count统计word中各字母数量
const count = {};
for (let c of word) {
count[c] ? count[c]++ : (count[c] = 1);
}
// ans保存题解
let ans = 0;
// 滑动窗口左指针的移动范围为 0~maxI
let maxI = content.length - word.length;
outer: for (let i = 0; i <= maxI; i++) {
const countb = JSON.parse(JSON.stringify(count));
const letters = {};
for (let j = i; j < i + word.length; j++) {
const c = content[j];
// 如果滑动窗口j位置字母不属于word，则说明当前滑动窗口内的单词肯定不是word新词，且j之前的所有滑动窗口都毁了，只能从j之后滑动窗口重新开始
if (count[c] === undefined) {
i = j;
continue outer;
}
// 如果滑动窗口内部字母是word中的，且在规定数量内
if (countb[c] > 0) {
// 出现了一个，则规定数量--
countb[c]--;
// 记录content中出现的字母的位置
letters[c] ? letters[c].push(j) : (letters[c] = [j]);
} else {
// 如果滑动窗口j位置字母属于word，但是此时由于j位置字母的加入，导致滑动窗口内部对应字母数量超过了word，则说明当前滑动窗口内单词肯定不是word新词
// 且我们应该让之后的滑动窗口内部该字母数量不能超，因此下一个滑动窗口的起始位置应该是该字母在当前滑动窗口第一次出现位置的下一个位置开始滑动
i = letters[c][0];
continue outer;
}
}
ans++;
}
return ans;
}
传统式
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const content = lines[0];
const word = lines[1];
console.log(getResult(content, word));
lines.length = 0;
}
});
function getResult(content, word) {
// 如果content长度小于word，则直接返回0
if (content.length < word.length) {
return 0;
}
// ans保存题解
let ans = 0;
// total记录word字母总数
let total = word.length;
// count统计word中各字母数量
const count = {};
for (let c of word) {
count[c] ? count[c]++ : (count[c] = 1);
}
// 初始滑动窗口内部字母遍历
for (let i = 0; i < word.length; i++) {
const c = content[i];
if (count[c] !== undefined && count[c]-- > 0) {
total--;
}
}
if (total === 0) ans++;
// 滑动窗口左指针的移动范围为 0~maxI
let maxI = content.length - word.length;
for (let i = 1; i <= maxI; i++) {
const remove_c = content[i - 1];
const add_c = content[i + word.length - 1];
if (count[remove_c] !== undefined && count[remove_c]++ >= 0) {
total++;
}
if (count[add_c] !== undefined && count[add_c]-- > 0) {
total--;
}
if (total === 0) ans++;
}
return ans;
}
Java算法源码
Java这里只实现一个传统式的，因为感觉跳跃式的性能提升局限性太大。
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String content = sc.next();
String word = sc.next();
System.out.println(getResult(content, word));
}
public static int getResult(String content, String word) {
// 如果content长度小于word，则直接返回0
if (content.length() < word.length()) {
return 0;
}
// ans保存题解
int ans = 0;
// total记录word字母总数
int total = word.length();
// count统计word中各字母数量
HashMap<Character, Integer> count = new HashMap<>();
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
count.put(c, count.getOrDefault(c, 0) + 1);
}
// 初始滑动窗口内部字母遍历
for (int i = 0; i < word.length(); i++) {
Character c = content.charAt(i);
if (count.containsKey(c)) {
if (count.get(c) > 0) {
total--;
}
count.put(c, count.get(c) - 1);
}
}
if (total == 0) ans++;
// 滑动窗口左指针的移动范围为 0~maxI
int maxI = content.length() - word.length();
for (int i = 1; i <= maxI; i++) {
Character remove_c = content.charAt(i - 1);
Character add_c = content.charAt(i + word.length() - 1);
if (count.containsKey(remove_c)) {
if (count.get(remove_c) >= 0) {
total++;
}
count.put(remove_c, count.get(remove_c) + 1);
}
if (count.containsKey(add_c)) {
if (count.get(add_c) > 0) {
total--;
}
count.put(add_c, count.get(add_c) - 1);
}
if (total == 0) ans++;
}
return ans;
}
}
Python算法源码
content = input()
word = input()
def getResult(content, word):
# 如果content长度小于word，则直接返回0
if len(content) < len(word):
return 0
# ans保存题解
ans = 0
# total记录word字母总数
total = len(word)
# count统计word中各字母数量
count = {}
for c in word:
if count.get(c) is None:
count[c] = 1
else:
count[c] += 1
# 初始滑动窗口内部字母遍历
for i in range(len(word)):
c = content[i]
if count.get(c) is not None:
if count[c] > 0:
total -= 1
count[c] -= 1
if total == 0:
ans += 1
# 滑动窗口左指针的移动范围为 0~maxI
maxI = len(content) - len(word) + 1
for i in range(1, maxI):
remove_c = content[i - 1]
add_c = content[i + len(word) - 1]
if count.get(remove_c) is not None:
if count[remove_c] >= 0:
total += 1
count[remove_c] += 1
if count.get(add_c) is not None:
if count[add_c] > 0:
total -= 1
count[add_c] -= 1
if total == 0:
ans += 1
return ans
print(getResult(content, word))免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0