Word Squares

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Valid Word Square

題目連結:https://leetcode.com/problems…

暴力遍歷,一個一個檢檢視符不符合要求。

    public boolean validWordSquare(List<String> words) {
/* words[i][j] == words[j][i]
* j >= len(words) or i >= len(words[j]) return false
*/
for(int i = 0; i < words.size(); i  ) {
String word = words.get(i);
for(int j = 0; j < word.length(); j  ) {
if(j >= words.size() || i >= words.get(j).length()) return false;
if(word.charAt(j) != words.get(j).charAt(i)) return false;
}
}
return true;
}

Word Squares

題目連結:https://leetcode.com/problems…

這道題如果用上一題的方法,一個一個試的話,時間複雜度太高。所以要另想辦法。
首先這種需要求出所有結果的題,一般都是用dfs(backtracking)的。然後這道題的思路是單詞一個一個確定。因為題目已經說了word的長度範圍是1到5,最多考慮五個單詞即可。

第一個單詞:””為字首,在words陣列裡隨便取一個word1,確定長度

第二個單詞:在剩下的words裡取出一個以word1[1]為字首的word2

第三個單詞:在剩下的裡取出一個以word1[2] word2[2]為字首的word3

第四個單詞:在剩下的裡取出一個以word1[3] word2[3] word3[3]為字首的word4

第五個單詞:在剩下的裡取出一個以word1[4] word2[4] word3[4] word4[4]為字首的word5

所以這題需要快速的找到字首,那麼可以想到用hashmap或者trie tree。題目說了單詞沒有duplication,省去了查重的過程。

遍歷words,把其中的一個單詞當作1st word

找到第二個單詞,加到square裡面,接著找第三個單詞……這是個backtracking的過程,如果prefix不在trie tree裡面直接return

找第二個,第三個,。。。單詞的過程用的是bfs,已經知道prefix之後,根據prefix找到trie tree裡面對應的node,從改node開始bfs走剩下的長度,找到所有可能的node,檢查這些node是否是單詞的末尾,是的話就放入list裡面,給上面dfs的method來用

public class Solution {
public List<List<String>> wordSquares(String[] words) {
// hashmap or trie tree
TrieNode root = buildTrieTree(words);
// traverse all word int words, for the 1st word
for(String word : words) {
// len(word) == 1, itself is square
if(word.length() == 1) {
List<String> cur = new ArrayList();
cur.add(word);
result.add(cur);
continue;
}
List<String> square = new ArrayList();
square.add(word);
dfs(root, square);
}
return result;
}
List<List<String>> result = new ArrayList();
/* from the idx position in words
* 1st word: a = words[i]
* 2nd word: b prefix = a.charAt(1)
* 3rd word: c prefix = a.charAt(2)   b.charAt(2)
* 4th word: d prefix = a.charAt(3)   b.charAt(3)   c.charAt(3)
* 5th word: e prefix = a.charAt(4)   b.charAt(4)   c.charAt(4)   d.charAt(4)
*/
private void dfs(TrieNode root, List<String> square) {
int len = square.get(0).length();
int prefix_length = square.size();
if(len == prefix_length) {
result.add(new ArrayList(square));
return;
}
String prefix = "";
// find supposed prefix
for(int i = 0; i < prefix_length; i  ) prefix  = square.get(i).charAt(prefix_length);
// find word with that prefix in trie tree
TrieNode node = root;
for(int i = 0; i < prefix.length(); i  ) {
if(node.children[getIndex(prefix.charAt(i))] == null) return;
node = node.children[getIndex(prefix.charAt(i))];
}
List<String> next = bfs(node, len - prefix_length);
if(next.size() == 0) return;
for(String s : next) {
square.add(s);
dfs(root, square);
square.remove(square.size() - 1);
}
}
// find all possible words with certain prefix
private List<String> bfs(TrieNode node, int left) {
List<String> possible = new ArrayList();
Queue<TrieNode> q = new LinkedList();
q.offer(node);
while(left-- > 0) {
if(q.isEmpty()) break;
for(int j = q.size(); j > 0; j--) {
TrieNode cur = q.poll();
for(int i = 0; i < 26; i  ) {
if(cur.children[i] != null) q.offer(cur.children[i]);
}
}
}
for(TrieNode cur : q) {
if(cur.word != null) possible.add(cur.word);
}
return possible;
}
private int getIndex(char c) {
return c - 'a';
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = "";
}
private TrieNode buildTrieTree(String[] words) {
TrieNode root = new TrieNode();
for(String word : words) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i  ) {
if(cur.children[getIndex(word.charAt(i))] == null) {
cur.children[getIndex(word.charAt(i))] = new TrieNode();
}
cur = cur.children[getIndex(word.charAt(i))];
}
cur.word = word;
}
return root;
}
}

看了discussion的方法,直接在構造trie的時候,在node裡面加上以它為prefix所有可能的word,這樣多加了一個List<String>的空間,但是省去了上面bfs找單詞的時間。

public class Solution {
public List<List<String>> wordSquares(String[] words) {
// hashmap or trie tree
TrieNode root = buildTrieTree(words);
// traverse all word int words, for the 1st word
for(String word : words) {
// len(word) == 1, itself is square
if(word.length() == 1) {
List<String> cur = new ArrayList();
cur.add(word);
result.add(cur);
continue;
}
List<String> square = new ArrayList();
square.add(word);
dfs(root, square);
}
return result;
}
List<List<String>> result = new ArrayList();
private void dfs(TrieNode root, List<String> square) {
int len = square.get(0).length();
if(len == square.size()) {
result.add(new ArrayList(square));
return;
}
// find all words with prefix
List<String> next = findWords(root, square);
for(String s : next) {
square.add(s);
dfs(root, square);
square.remove(square.size() - 1);
}
}
private List<String> findWords(TrieNode node, List<String> square) {
String prefix = "";
int prefix_length = square.size();
// find supposed prefix
for(int i = 0; i < prefix_length; i  ) prefix  = square.get(i).charAt(prefix_length);
// find word with that prefix in trie tree
for(int i = 0; i < prefix.length(); i  ) {
if(node.children[getIndex(prefix.charAt(i))] == null) return new ArrayList();
node = node.children[getIndex(prefix.charAt(i))];
}
return node.wordsWithPrefix;
}
private int getIndex(char c) {
return c - 'a';
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
List<String> wordsWithPrefix = new ArrayList();
}
private TrieNode buildTrieTree(String[] words) {
TrieNode root = new TrieNode();
for(String word : words) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i  ) {
if(cur.children[getIndex(word.charAt(i))] == null) {
cur.children[getIndex(word.charAt(i))] = new TrieNode();
}
cur = cur.children[getIndex(word.charAt(i))];
cur.wordsWithPrefix.add(word);
}
}
return root;
}
}

Trie Tree的構造方法

cc150上面給了Trie和TrieNode的構造方法。感覺lc裡面主要是高清TrieNode的fields,以及對應的build一個Trie的方法。lc上一共7道trie的題,出現過的TrieNode的fields不同的選擇好像就3種。
首先children是肯定都需要的,兩種:array(TrieNode[])或者HashMap(Map<Character, TrieNode>)。都可以用,但是好像lc上的題基本用的都是array,character的範圍比較小用array還是比較省空間。

然後還用到的fields有:isWord(boolean:結尾,判斷是否形成一個單詞), word(String:結尾,形成的單詞)以及startsWith(List<String>:以走到當前的TrieNode形成的String為prefix,所有的word)
如果題目只要求判斷單詞在不在字典裡,isWord就夠了。
如果題目要求返回String,那麼一般用word。
如果題目要求返回所有以特定的prefix開頭的單詞,那麼可以用startsWith。

相關文章

程式語言 最新文章