[LeetCode] 425. Word Squares

ranwu 发布于2019-08-16 13:41 / 1184人阅读

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, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.
Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Reference:
https://leetcode.com/problems...

Solution - Trie+DFS

class Solution {
    public List> wordSquares(String[] words) {
        List> res = new ArrayList<>();
        if (words == null || words.length == 0) return res;
        int len = words[0].length();
        List temp = new ArrayList<>();
        Trie trie = new Trie(words);
        for (String word: words) {
            temp.add(word);
            dfs(trie, len, temp, res);
            temp.remove(temp.size()-1);
        }
        return res;
    }
    
    private void dfs(Trie trie, int len, List temp, List> res) {
        int size = temp.size();
        if (size == len) {
            res.add(new ArrayList<>(temp));
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (String str: temp) {
            sb.append(str.charAt(size));
        }
        String prefix = sb.toString();
        List words = trie.getWords(prefix);
        for (String word: words) {
            temp.add(word);
            dfs(trie, len, temp, res);
            temp.remove(temp.size()-1);
        }
    }
}

class Trie {
    TrieNode root;
    public Trie(String[] strs) {
        root = new TrieNode();
        for (String str: strs) {
            TrieNode cur = root;
            for (char ch: str.toCharArray()) {
                int index = ch-"a";
                if (cur.children[index] == null) cur.children[index] = new TrieNode();
                cur.children[index].words.add(str);
                cur = cur.children[index];
            }
        }
    }
    
    public List getWords(String prefix) {
        List res = new ArrayList<>();
        TrieNode cur = root;
        for (char ch: prefix.toCharArray()) {
            int index = ch-"a";
            if (cur.children[index] == null) return res;
            cur = cur.children[index];
        }
        res.addAll(cur.words);
        return res;
    }
}

class TrieNode {
    TrieNode[] children;
    List words;
    public TrieNode() {
        children = new TrieNode[26];
        words = new ArrayList<>();
    }
}

私有云 GPU服务器 Squares ftp425错误 LeetCode 425处理器 webrtc

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

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

425 Word Squares

摘要：我们要满足都可以作为开头的部分。按照代码的逻辑，走一遍填写好每一步被更新的样子。开始结束同一层从左向右走的时候会不断增长，直到最后形成以个单词相应位置长度加一，更新重新进行下一次的搜索。题目描述请见leetcode 425 w a l l a r e a l e a d l a d y 在给定的词典里，找到一些单词，组成一个square, 第i行和第i列一样。(0,0) 这个点找到满...

luzhuqun 2019-08-14 17:38 评论0 收藏0
Word Squares

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

JerryZou 2019-08-14 17:19 评论0 收藏0
Leetcode PHP题解--D34 977. Squares of a Sorted Array

摘要：题目链接题目分析本题比较简单。对给定数组的每一个数字的平方。并对结果进行排序。思路遍历每一个元素，相乘自身。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 977. Squares of a Sorted Array 题目链接 977. Squares of a Sorted Array 题目分析本题比较简单。对给定数组的每一个数字的平方。并对结果进行排序。思路遍历每一个元素，...

Kaede 2019-07-01 12:41 评论0 收藏0
[Leetcode] Perfect Squares 完美平方数

摘要：动态规划复杂度时间空间思路如果一个数可以表示为一个任意数加上一个平方数，也就是，那么能组成这个数最少的平方数个数，就是能组成最少的平方数个数加上因为已经是平方数了。 Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4...

Moxmi 2019-08-14 12:33 评论0 收藏0
[LeetCode] 279. Perfect Squares

Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Exampl...

mist14 2019-08-16 13:57 评论0 收藏0