Word Squares

JerryZou 發(fā)布于2019-08-14 17:19 / 1121人閱讀

摘要：題目鏈接暴力遍歷，一個(gè)一個(gè)檢查看符不符合要求。首先這種需要求出所有結(jié)果的題，一般都是用的。因?yàn)轭}目已經(jīng)說了的長度范圍是到，最多考慮五個(gè)單詞即可。首先是肯定都需要的，兩種或者。如果題目要求返回所有以特定的開頭的單詞，那么可以用。

Valid Word Square

題目鏈接：https://leetcode.com/problems...

暴力遍歷，一個(gè)一個(gè)檢查看符不符合要求。

    public boolean validWordSquare(List 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...

這道題如果用上一題的方法，一個(gè)一個(gè)試的話，時(shí)間復(fù)雜度太高。所以要另想辦法。
首先這種需要求出所有結(jié)果的題，一般都是用dfs(backtracking)的。然后這道題的思路是單詞一個(gè)一個(gè)確定。因?yàn)轭}目已經(jīng)說了word的長度范圍是1到5，最多考慮五個(gè)單詞即可。

第一個(gè)單詞：""為前綴，在words數(shù)組里隨便取一個(gè)word1，確定長度

第二個(gè)單詞：在剩下的words里取出一個(gè)以word1[1]為前綴的word2

第三個(gè)單詞：在剩下的里取出一個(gè)以word1[2]+word2[2]為前綴的word3

第四個(gè)單詞：在剩下的里取出一個(gè)以word1[3]+word2[3]+word3[3]為前綴的word4

第五個(gè)單詞：在剩下的里取出一個(gè)以word1[4]+word2[4]+word3[4]+word4[4]為前綴的word5

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

遍歷words，把其中的一個(gè)單詞當(dāng)作1st word

找到第二個(gè)單詞，加到square里面，接著找第三個(gè)單詞......這是個(gè)backtracking的過程，如果prefix不在trie tree里面直接return

找第二個(gè)，第三個(gè)，。。。單詞的過程用的是bfs，已經(jīng)知道prefix之后，根據(jù)prefix找到trie tree里面對應(yīng)的node，從改node開始bfs走剩下的長度，找到所有可能的node，檢查這些node是否是單詞的末尾，是的話就放入list里面，給上面dfs的method來用

public class Solution {
    public List> 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 cur = new ArrayList();
                cur.add(word);
                result.add(cur);
                continue;
            }
            List square = new ArrayList();
            square.add(word);
            dfs(root, square);
        }
        
        return result;
    }
    
    List> 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 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 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 bfs(TrieNode node, int left) {
        List possible = new ArrayList();
        Queue 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的方法，直接在構(gòu)造trie的時(shí)候，在node里面加上以它為prefix所有可能的word，這樣多加了一個(gè)List的空間，但是省去了上面bfs找單詞的時(shí)間。

public class Solution {
    public List> 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 cur = new ArrayList();
                cur.add(word);
                result.add(cur);
                continue;
            }
            List square = new ArrayList();
            square.add(word);
            dfs(root, square);
        }
        
        return result;
    }
    
    List> result = new ArrayList();

    private void dfs(TrieNode root, List square) {
        int len = square.get(0).length();
        if(len == square.size()) {
            result.add(new ArrayList(square));
            return;
        }
        // find all words with prefix
        List next = findWords(root, square);
        for(String s : next) {
            square.add(s);
            dfs(root, square);
            square.remove(square.size() - 1);
        }
    }
    
    private List findWords(TrieNode node, List 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 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的構(gòu)造方法

cc150上面給了Trie和TrieNode的構(gòu)造方法。感覺lc里面主要是高清TrieNode的fields，以及對應(yīng)的build一個(gè)Trie的方法。lc上一共7道trie的題，出現(xiàn)過的TrieNode的fields不同的選擇好像就3種。
首先children是肯定都需要的，兩種：array(TrieNode[])或者HashMap(Map)。都可以用，但是好像lc上的題基本用的都是array，character的范圍比較小用array還是比較省空間。

然后還用到的fields有：isWord(boolean：結(jié)尾，判斷是否形成一個(gè)單詞), word(String：結(jié)尾，形成的單詞)以及startsWith(List：以走到當(dāng)前的TrieNode形成的String為prefix，所有的word)
如果題目只要求判斷單詞在不在字典里，isWord就夠了。
如果題目要求返回String，那么一般用word。
如果題目要求返回所有以特定的prefix開頭的單詞，那么可以用startsWith。