資訊專欄INFORMATION COLUMN
摘要：我們要滿足都可以作為開頭的部分。按照代碼的邏輯，走一遍填寫好每一步被更新的樣子。開始結(jié)束同一層從左向右走的時候會不斷增長，直到最后形成以個單詞相應(yīng)位置長度加一，更新重新進行下一次的搜索。
題目描述請見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 結(jié)束 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 結(jié)束 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66712.html
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...
摘要：題目鏈接暴力遍歷，一個一個檢查看符不符合要求。首先這種需要求出所有結(jié)果的題，一般都是用的。因為題目已經(jīng)說了的長度范圍是到，最多考慮五個單詞即可。首先是肯定都需要的，兩種或者。如果題目要求返回所有以特定的開頭的單詞，那么可以用。 Valid Word Square 題目鏈接：https://leetcode.com/problems... 暴力遍歷，一個一個檢查看符不符合要求。 ...
摘要：中的注釋是以開頭，并且一直延申到該文本結(jié)束為止。例如的長度為使用過大的索引會產(chǎn)生一個錯誤但是在切片中，越界索引會被自動處理中的字符串不能被修改，它們是的。其中最常用的列表，可以通過方括號括起逗號分隔的一組值得到。 在下面的例子中通過提示符（>>>與...）的出現(xiàn)與否來區(qū)分輸入和輸出：如果你想復(fù)現(xiàn)這些例子，當(dāng)提示符出現(xiàn)后，你必須在提示符后鍵入例子中的每一個詞；不以提示符開頭的那些行是解釋...
閱讀 930·2021-11-16 11:45
閱讀 2135·2021-10-09 09:44
閱讀 1354·2019-08-30 14:03
閱讀 1138·2019-08-26 18:28
閱讀 3338·2019-08-26 13:50
閱讀 1728·2019-08-23 18:38
閱讀 3459·2019-08-23 18:22
閱讀 3606·2019-08-23 15:27
