社区讨论
js解题感觉思路都对,但是就是过不了,求大神们帮忙看看
P4407[JSOI2009] 电子字典参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo38kmx7
- 此快照首次捕获于
- 2023/10/24 02:33 2 年前
- 此快照最后确认于
- 2023/10/24 02:33 2 年前
思路是字典树
JAVASCRIPTconst readline = require('readline');
const rl = readline.createInterface({
input:process.stdin,
output:process.stdout
});
let countLine = 1, tireTree = { index: 0 }, inx = 0, record = "", mem = [], res = 0;
let n, m;
rl.on('line', function(line) {
if(countLine === 1) {
//求和
line = line.split(' ');
n = parseInt(line[0]);
m = parseInt(line[1]);
} else {
// 处理input
if (n-- > 0) {
insert(line);
} else {
//查找本身
m--;
res = 0;
record = line;
dfs(tireTree, 0, false);
console.log(res);
res = 0;
mem = [];
}
if (m <= 0)
rl.close();
}
countLine++;
})
function dfs(x, y, flag) {
if (res === -1)// 原样匹配过了
return;
//找到了
if (x.finished && y === record.length) {
if (flag) {// 操作过了
if (!mem[x.index]) {
mem[x.index] = true;
res++;
}
}
else {
res = -1;
}
return;
}
//将record在此刻位置【y】前增加一个,由于可以增加任意字符,所以但凡下一层有节点的字典树路径都可以匹配。
if (!flag && x.children) {
for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
let t = String.fromCharCode(i);
if (x.children[t]) {
dfs(x.children[t], y, true);
}
}
}
if (y >= record.length) {
return;
}
if (!flag) {
//删
if (y < record.length)
dfs(x, y + 1, true);
//改
if (x.children)
for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
let t = String.fromCharCode(i);
if (t !== record[y] && x.children[t]) {//改成和原来一样的就没有意义了
dfs(x.children[t], y + 1, true);
}
}
}
if (x.children && x.children[record[y]]) {
dfs(x.children[record[y]], y + 1, flag)
}
}
function insert(item) {
item = item.split('')
let p = tireTree, inx = 0;// p用于遍历存储,
// before用于存储:当前字符之前的最长词链的单词数
item.forEach((it, index) => {
// 存储的过程
if (!p.children) {
p.children = {};
}
p = p.children;
if (!p[it]) {
p[it] = {};
p[it].index = ++inx;
}
p = p[it];
if (index === item.length - 1) {//标记最后一个字符
p.finished = true;
}
})
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...