425 Word Squares

luzhuqun 发布于2019-08-14 17:38 / 3004人阅读

摘要：我们要满足都可以作为开头的部分。按照代码的逻辑，走一遍填写好每一步被更新的样子。开始结束同一层从左向右走的时候会不断增长，直到最后形成以个单词相应位置长度加一，更新重新进行下一次的搜索。

题目描述请见leetcode 425

w a l l
a r e a
l e a d
l a d y

在给定的词典里，找到一些单词，组成一个square, 第i行和第i列一样。
(0,0) 这个点找到满足条件的,我们选择w。
(0,1) 我们要满足wa, a都可以作为开头的部分。
(0,2) 我们要满足wal, l都可以作为开头的部分。

按照代码的逻辑，走一遍test case, 填写好prefix[]每一步被更新的样子。

第0行。     
开始    prefix[root, root, root, root] 
(0, 0) prefix[root, root, root, root]  (root.w, root.w)  root[0] = w, root[0] = w
(0, 1) prefix[w, root, root, root]     (w.a, root.a)     root[0] = wa, root[1] = a
(0, 2) prefix[wa, a, root, root]     (wa.l, root.l)     root[0] = wal, root[2] = l
(0, 3) prefix[wal, a, l, root]     (wal.l, root.l)     root[0] = wall, root[3] = l
结束     prefix[wall, a, l, l] 

第1行。
开始    prefix[wall, a, l, l]

(1,1)  prefix[wall, a, l, l]       (a.r, a.r)     root[1] = ar,  root[1] = ar
(1,2)  prefix[wall, ar, l, l]      (ar.e, l.e)    root[1] = are, root[2] = le
(1,3)  prefix[wall, are, le, l]      (are.a, l.a)    root[1] = area, root[3] =la
结束    prefix[wall, area, le, la]

public class Solution {
    class Node{
        String word = null;
        Node[] kids = new Node[26];
    }
    
    private Node root = new Node();
    
    private void buildTrie(String word, Node par){
        for(char c: word.toCharArray()){
            int idx = c -"a";
            if(par.kids[idx] == null) par.kids[idx] = new Node();
            par = par.kids[idx];
        }
        par.word = word;
    }
    
    private void findAllSquares(int row , int col, Node[] prefix, List> res){
        if(row == prefix.length){
            List temp = new ArrayList();
            for(int i=0; i> wordSquares(String[] words) {
        List> res = new ArrayList>();
        if(words == null || words.length == 0 || words[0] == null || words[0].length() == 0) return res;
        for(String word: words){
            buildTrie(word, root);
        }
        Node[] prefix = new Node[words[0].length()];
        Arrays.fill(prefix, root);
        findAllSquares(0, 0, prefix, res);
        return res;
    }
}

GPU云服务器云服务器 Squares ftp425错误 425处理器 webrtc Word

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66712.html

[LeetCode] 425. Word Squares

Problem Given a set of words (without duplicates), find all word squares you can build from them. A sequence of words forms a valid word square if the kth row and column read the exact same string, wh...

ranwu 2019-08-16 13:41 评论0 收藏0
Word Squares

摘要：题目链接暴力遍历，一个一个检查看符不符合要求。首先这种需要求出所有结果的题，一般都是用的。因为题目已经说了的长度范围是到，最多考虑五个单词即可。首先是肯定都需要的，两种或者。如果题目要求返回所有以特定的开头的单词，那么可以用。 Valid Word Square 题目链接：https://leetcode.com/problems... 暴力遍历，一个一个检查看符不符合要求。 ...

JerryZou 2019-08-14 17:19 评论0 收藏0
python学习：python的正式介绍

摘要：中的注释是以开头，并且一直延申到该文本结束为止。例如的长度为使用过大的索引会产生一个错误但是在切片中，越界索引会被自动处理中的字符串不能被修改，它们是的。其中最常用的列表，可以通过方括号括起逗号分隔的一组值得到。在下面的例子中通过提示符（>>>与...）的出现与否来区分输入和输出：如果你想复现这些例子，当提示符出现后，你必须在提示符后键入例子中的每一个词；不以提示符开头的那些行是解释...

suxier 2019-07-31 10:22 评论0 收藏0