社区讨论

js解题感觉思路都对,但是就是过不了,求大神们帮忙看看

P4407[JSOI2009] 电子字典参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo38kmx7
此快照首次捕获于
2023/10/24 02:33
2 年前
此快照最后确认于
2023/10/24 02:33
2 年前
查看原帖
思路是字典树
JAVASCRIPT
const 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 条回复,欢迎继续交流。

正在加载回复...