0

请注意，下面的代码在控制台中显示了数组，而不是在代码段输出中

var nodes = ["maria", "mary", "marks", "michael"];

function insert_word(split_nodes) {
  var rest = [];
  for (var i = 0; i < split_nodes.length; i++) {
    //console.log(current);
    var word = split_nodes[i];
    var letters = word.split("");
    var current = rest;
    console.log(current);
    for (var j = 0; j < letters.length; j++) {
      var character = letters[j];
      var position = current[character];
      if (position == null) {
        current = current[character] = j == letters.length - 1 ? 0 : {};
      } else {
        current = current[character];
      }
    }
  }
}
insert_word(nodes);

上面输出这个

M :{a : {r :{i :{a :0},
    k :0,   
    y :
    },
},
    i :{c :{h :{a :{e :{l :0}}}}}}}

但我想输出这个：

M :{ar:{ia:0,
    k :0,   
    y :0
    },
 ichael :0
}

谁能帮我从我的代码中找出这个输出？我怎么能用这段代码做后缀？

4

1 回答 1

0

该解决方案为带有属性 的结束指示符采用了一个明显改变的对象结构isWord，因为原始结构不反映像'marc'and之类的条目'marcus'，因为如果仅'marc'使用，树末尾的零表示单词的结尾，但它不允许添加子字符串，因为该属性是基元而不是对象。

基本上，这个解决方案首先创建一个带有单个字母的完整树，然后连接所有只有一个子对象的属性。

function join(tree) {
    Object.keys(tree).forEach(key => {
        var object = tree[key],
            subKeys = Object.keys(object),
            joinedKey = key,
            found = false;    

        if (key === 'isWord') {
            return;
        }
        while (subKeys.length === 1 && subKeys[0] !== 'isWord') {
            joinedKey += subKeys[0];
            object = object[subKeys[0]];
            subKeys = Object.keys(object);
            found = true;
        }
        if (found) {
            delete tree[key];
            tree[joinedKey] = object;
        }
        join(tree[joinedKey]);
    });
}

var node = ["maria", "mary", "marks", "michael"],
    tree = {};

node.forEach(string => [...string].reduce((t, c) => t[c] = t[c] || {}, tree).isWord = true);
console.log(tree);

join(tree);
console.log(tree);
.as-console-wrapper { max-height: 100% !important; top: 0; }

一种递归单通道方法，具有用于将单词插入更新节点的树的功能。

它的工作原理

  • string使用对象的所有键检查给定，如果string从实际键开始，则使用部分字符串和 trie 的嵌套部分进行递归调用。

  • 否则，它会检查键和字符串中有多少字符相同。

    然后它检查计数器并创建一个具有公共部分和两个节点的新节点，旧节点内容和字符串的新节点。

    由于新节点，旧节点不再需要并被删除，并且迭代通过返回true检查而停止update。

  • 如果没有发生更新，则分配一个以字符串为键、零为值的新属性。

function insertWord(tree, string) {
    var keys = Object.keys(tree),
        updated = keys.some(function (k) {
            var i = 0;

            if (string.startsWith(k)) {
                insertWord(tree[k], string.slice(k.length));
                return true;
            }
            while (k[i] === string[i] && i < k.length) {
                i++;
            }
            if (i) {
                tree[k.slice(0, i)] = { [k.slice(i)]: tree[k], [string.slice(i)]: 0 };
                delete tree[k];
                return true;
            }
        });

    if (!updated) {            
        tree[string] = 0;
    }
}

var words = ["maria", "mary", "marks", "michael"],
    tree = {};

words.forEach(insertWord.bind(null, tree));
console.log(tree);

insertWord(tree, 'mara');
console.log(tree);
.as-console-wrapper { max-height: 100% !important; top: 0; }

于 2018-02-03T17:40:14.887 回答