Leetcode 1268 搜索推荐系统 字典树DFS

　　JAVA：

public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Node head = initTree(products);
        List<List<String>> reList = new ArrayList<List<String>>(searchWord.length());
        if (products == null || products.length == 0) return reList;
        for (int i = 1; i <= searchWord.length(); i++) {
            String str = searchWord.substring(0, i);
            List<String> list = new LinkedList<String>();
            search(str, head, list);
            reList.add(list);
        }
        return reList;
    }

    //查询
    private final void search(String target, Node node, List<String> reList) {
        Node begin = getBegin(node, target);
        if (begin == null) return;
        if (begin.isEnd) reList.add(begin.str);
        searchList(begin, reList);
    }

    // DFS,按字典序取值
    private final void searchList(Node node, List<String> reList) {
        for (int i = 0; i < 26; i++) {
            if (reList.size() == 3) return;
            if (node.childs[i] == null || node.childs[i].nums == 0) continue;
            if (node.childs[i].isEnd) reList.add(node.childs[i].str);
            searchList(node.childs[i], reList);
        }
    }

    //跳过前缀
    private final Node getBegin(Node head, String str) {
        char[] cs = str.toCharArray();
        for (char c : cs) {
            if (head.childs[c - 'a'] == null) return null;
            head = head.childs[c - 'a'];
        }
        return head;
    }

    //初始化字典树
    private final Node initTree(String[] strArr) {
        Node head = new Node();
        for (int i = 0; i < strArr.length; i++) insertStr(head, strArr[i]);
        return head;
    }

    //字符串插入字典树
    private final void insertStr(Node head, String str) {
        char[] chars = str.toCharArray();
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            int point = chars[i] - 'a';
            if (head.childs[point] == null) head.childs[point] = new Node();
            else head.childs[point].nums++;
            head = head.childs[point];
        }
        head.isEnd = true;
        head.str = str;
    }

    //字典树节点
    private class Node {
        int nums;
        Node[] childs;
        boolean isEnd;
        String str;

        Node() {
            this.nums = 1;
            this.childs = new Node[26];
            this.isEnd = false;
        }
    }

　　JS：

var suggestedProducts = function (products, searchWord) {
    let re = [], head = initTree(products);
    for (let i = 1; i <= searchWord.length; i++) {
        let currStr = searchWord.substring(0, i);
        let currRe = [];
        searchList(head, currStr, currRe);
        re.push(currRe);
    }
    return re;
};

var searchList = function (head, str, reArr) {
    let currHead = getHead(head, str);
    if (!currHead) return;
    if (currHead.isEnd) reArr.push(currHead.str);
    search(currHead, reArr);
}

var search = function (head, reArr) {
    for (let i = 0; i < 26; i++) {
        if (reArr.length == 3) return;
        if (!head.childs[i]) continue;
        if (head.childs[i].isEnd) reArr.push(head.childs[i].str);
        search(head.childs[i], reArr);
    }
}

var getHead = function (head, str) {
    for (let i = 0; i < str.length; i++) {
        let ch = str.charAt(i), chPoint = ch.charCodeAt()-97;
        if (!head.childs[chPoint]) return null;
        else head = head.childs[chPoint];
    }
    return head;
}

var initTree = function (strArr) {
    let head = new Node();
    for (let i = 0; i < strArr.length; i++) insertNode(head, strArr[i]);
    return head;
}

var insertNode = function (head, str) {
    for (let i = 0; i < str.length; i++) {
        let ch = str.charAt(i), chPoint = ch.charCodeAt()-97;
        if (!head.childs[chPoint]) head.childs[chPoint] = new Node();
        else head.childs[chPoint].nums = head.childs[chPoint].nums + 1;
        head = head.childs[chPoint];
    }
    head.isEnd = true;
    head.str = str;
}

var Node = function () {
    this.nums = 1;
    this.childs = new Array(26);
    this.isEnd = false;
    this.str = '';
}