Java 15ms Easiest Solution (100.00%)


  • 372

    Backtracking + Trie


    Intuitively, start from every cell and try to build a word in the dictionary. Backtracking (dfs) is the powerful way to exhaust every possible ways. Apparently, we need to do pruning when current character is not in any word.

    1. How do we instantly know the current character is invalid? HashMap?
    2. How do we instantly know what's the next valid character? LinkedList?
    3. But the next character can be chosen from a list of characters. "Mutil-LinkedList"?

    Combing them, Trie is the natural choice. Notice that:

    1. TrieNode is all we need. search and startsWith are useless.
    2. No need to store character at TrieNode. c.next[i] != null is enough.
    3. Never use c1 + c2 + c3. Use StringBuilder.
    4. No need to use O(n^2) extra space visited[m][n].
    5. No need to use StringBuilder. Storing word itself at leaf node is enough.
    6. No need to use HashSet to de-duplicate. Use "one time search" trie.

    For more explanations, check out dietpepsi's blog.


    Code Optimization


    UPDATE: Thanks to @dietpepsi we further improved from 17ms to 15ms.

    1. 59ms: Use search and startsWith in Trie class like this popular solution.
    2. 33ms: Remove Trie class which unnecessarily starts from root in every dfs call.
    3. 30ms: Use w.toCharArray() instead of w.charAt(i).
    4. 22ms: Use StringBuilder instead of c1 + c2 + c3.
    5. 20ms: Remove StringBuilder completely by storing word instead of boolean in TrieNode.
    6. 20ms: Remove visited[m][n] completely by modifying board[i][j] = '#' directly.
    7. 18ms: check validity, e.g., if(i > 0) dfs(...), before going to the next dfs.
    8. 17ms: De-duplicate c - a with one variable i.
    9. 15ms: Remove HashSet completely. dietpepsi's idea is awesome.

    The final run time is 15ms. Hope it helps!


    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs (board, i, j, root, res);
            }
        }
        return res;
    }
    
    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) {   // found one
            res.add(p.word);
            p.word = null;     // de-duplicate
        }
    
        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j ,p, res); 
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
        board[i][j] = c;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
           }
           p.word = w;
        }
        return root;
    }
    
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    

  • 17
    N
    This post is deleted!

  • 0

    @jewelolol thanks for your feedback:) Glad to hear that it helps!


  • 0
    Y

    this is so trie, impressed and upvoted


  • 0
    Y

    @yavinci, as a tiny little suggestion to further simplify the code, you can directly use root in calling DFS, like:

    TrieNode root = buildTrie(words);
            dfs(board, i, j, root, res);

  • 0

    @yanggao, thanks, makes sense :) I've updated my answer.


  • 20

    Good job! I like your solution!

    One other optimization

    You do not need Set<String> res to remove duplicate.
    You could just use List<String> res.
    Because the Trie has the ability of remove duplicate.
    All you need to do is to change

    if(p.word != null) res.add(p.word);
    

    Into

    if(p.word != null) {
        res.add(p.word);
        p.word = null;
    }
    

    Which removes the found word from the Trie.
    And you can just return res itself.

    It runs 16ms.

    See here


  • 0

    This is so clever @dietpepsi! I've updated my post and url. This is another time demonstrating that we should try to use List instead of Set or Map, given the same time complexity.


  • 0
    R

    very impressive!!!


  • 0
    I

    Love the analysis here! Thanks for sharing!


  • 0
    D

    good solution. Thanks for sharing.


  • 0
    L

    Impressive and very clean code. Thanks for sharing!


  • 4
    M

    one interesting point -- why 'toCharArray' is faster than 'chartAt'?
    By looking at the String class, 'charAt' directly accesses the element in the internal char array in the String while 'toCharArray' does an extra step to copy internal array. In this case, 'toCharArray' should be slower


  • -1
    C

    I tried to rewrite this to C++ but got runtime error. Anyone can see the error without debugging it? Thanks

    class TrieNode{
    public:
        string word;
        vector<TrieNode*> next;
        TrieNode()
        {
            next.assign(26,NULL);
        }
        
        void addWords(string words)
        {
            TrieNode *p = this;
            
            for (auto c:words)
            {
                int key = c-'a';
                if (p->next[key]==NULL)
                {
                    p->next[key]=new TrieNode();
                }
                p=p->next[key];
            }
            p->word=words;
        }
    };
    
    class Solution {
    
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            vector<string> res;
            
            if (words.empty()||board.empty())
               return res;
               
            int row=board.size(), col=board[0].size();
            TrieNode *root= new TrieNode();
            for (auto word: words)
            {
                root->addWords(word);
            }
            
            for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
            {
                dfs(board,res,r,c, root);
            }
            
            return res;
        }
        
        void dfs(vector<vector<char>>&board, vector<string> &res, int i, int j, TrieNode *p)
        {
            int key = board[i][j]-'a';
            
            if (p==NULL||p->next[key]==NULL||board[i][j]=='#')
               return;
               
            p=p->next[key];           
            
            if (p->word!="")
            {
                res.push_back(p->word);
                p->word="";
            }
            
            board[i][j] = '#';
            if(i>0)
            {
                dfs(board,res,i-1,j,p);
            }
            if (j>0)
            {
                dfs(board,res,i,j-1,p);
            }
            if (i<board.size()-1)
            {
                dfs(board,res,i+1,j,p);
            }
            
            if (j<board.size()-1)
            {
                dfs(board,res,i,j+1,p);
            }
            
            board[i][j]='a'+key;
        }
    
    };

  • 0
    O

    this improvement is amazing


  • 0
    Z

    Awesome idea.


  • 0
    Z

    Great job! Thank you for sharing.
    check if all the words have been found:
    if(res.size()==words.length) return res;
    before evoking
    dfs(board, i, j, root, res);
    might improve a little bit.
    }


  • 0
    W

    if(p.word != null) { // found one
    res.add(p.word);
    p.word = null; // de-duplicate
    //return
    }
    at this place, at first i added a return, but it gives me wrong answer. Why is that? Thank you.


  • 9

    Can you please explain the runtime complexity?


  • 0
    L

    Could you please do the complexity analysis of the solution ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.