一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 451|回复: 3
收起左侧

[Leetcode] LC 212 Trie 高赞答案解惑

[复制链接] |只看干货 |leetcode, 刷题
我的人缘0

升级   37.63%


分享帖子到朋友圈
yangmars | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (43)
 
 
14% (7)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
题目在这里: https://leetcode.com/problems/word-search-ii/
看了最高赞的答案(答案附在下面了),有一点不太理解的地方,假如给定以下matrix和array
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]["oath","hello","eat","rain"]
那么按照下面答案的buildTrie(),  matrix里面的第一个字符"o"就会满足 p.word != null 的条件,因为”hello"的最后一个字符o.word=“hello”,所以 hello会被加入 res里面,但是答案是没有这个“hello"的,而且这个解法也是没问题的。我想问下大家,我是哪里理解错了呢? 谢谢
public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res);
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res);
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
    board[j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next == null) p.next = new TrieNode();
            p = p.next;
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}



评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:加米lc 270, 求问closest binary search tree value思路
下一篇:【原创】自己刷题总结博客
我的人缘0

升级   41.14%

zea7ot 2020-8-10 14:12:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (663)
 
 
2% (19)    👎
本帖最后由 zea7ot 于 2020-8-10 14:23 编辑

我觉得这份代码错误还挺多的。
这是我总结的版本 - github
(好吧,原来是"[  i  ]"被解读成斜体的字符格式了lol)
dfs/backtrack方法里面,board的使用是有问题的,应该是board[  i  ] [j]。
buildTrie()方法里面,if(p.next[idx] = null) p.next[idx] = new TrieNode();

在buildTrie(String[] words)的时候,取一个word为例(为了避免混淆,我把此处的word写成WORD。而TrieNode里面的word字段仍然为word):
只有当某个该WORD走到底、也就是最后一个char的时候,对应的TrieNode的word字段才会被赋值成WORD,前面该WORD的所有字符(char)对应的TrieNode的word字段,都是String类型的默认初值,也就是null。
其目的就是标志该WORD在Trie里面已经搜索完整,可以用来判断。

本题使用String类型的word字段是一个很好的技巧,可以直接把word字段(的内容)拿来进行比较。


相比较而言,如果只是使用布尔类型的isWord就不具备这个功能。
这题目还涉及到单词的重复,为了避免重复加入到答案列表里面,直接把word字段再给抹除就不会被加入了。


评分

参与人数 2大米 +9 收起 理由
yangmars + 3 给你点个赞!
14417335 + 6

查看全部评分

回复

使用道具 举报

我的人缘0

升级   37.63%

 楼主| yangmars 2020-8-11 08:16:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (43)
 
 
14% (7)    👎
zea7ot 发表于 2020-8-10 14:12
我觉得这份代码错误还挺多的。
这是我总结的版本 - github。
(好吧,原来是"[  i  ]"被解读成斜体的字符 ...

搞明白了,p=p.next, 会把指针往下挪一层, 多谢!
回复

使用道具 举报

我的人缘0

升级   7.71%

fasionfans 2020-8-11 13:03:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (27)
 
 
0% (0)    👎
mark, will look later
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表