C++(52ms) / C# (528ms) explained solution using dfs and trie


  • 0
    O

    C++ version

    class TrieNode {
    public:
        string Value;
        TrieNode** Children;
        // Initialize your data structure here.
        TrieNode() {
            Children = new TrieNode*[26]();
            Value = "";
        }
        
        ~TrieNode(){
            for (int i = 0; i < 26; i++)
            {
                delete Children[i];
            }
            delete[] Children;
        }    
    };
    
    class Trie {
    public:
        TrieNode* root;
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode* pNode = root;
            int id;
            int n = word.size();
            for (int i = 0; i <n; ++i)
            {
              id = word[i] - 'a';
              if (pNode->Children[id] == NULL){
                    pNode->Children[id] = new TrieNode();
              }
              pNode = pNode->Children[id];
            } 
            
            pNode->Value = word;
        }
    };
    
    void findNextChar(int i, int j, int offset, int n, int m, vector<vector<char>>& board, TrieNode* node, int maxResults, vector<string>& res){
        // Ensure that all the words are not found and i,j are within the board's boundary
          if (res.size() < maxResults &&  i >= 0 && j >= 0 && i < n && j < m)
          {
             char cr = board[i][j];
            if (cr != '\0')
            {
                int index = cr - 'a';
                TrieNode* child = node->Children[index];
                if(child != NULL){
                    // flag the current character
                    board[i][j] = '\0';
                    if(child->Value.length() > 0){
                        // We found a word, add it to the results
                        res.push_back(child->Value);
                        // set the node value to empty string to avoid searching for it once again
                        child->Value = "";
                    }
                    
                    if(res.size() < maxResults){
                         // Search for next char (offset + 1) in neighborhood.
                        int newoffset = offset + 1;
                        findNextChar(i + 1, j, newoffset, n, m, board, child, maxResults, res);
                        findNextChar(i - 1, j, newoffset, n, m, board, child, maxResults, res);
                        findNextChar(i, j + 1, newoffset, n, m, board, child, maxResults, res);
                        findNextChar(i, j - 1, newoffset, n, m, board, child, maxResults, res); 
                    }
                    
                    // put back the current character value
                    board[i][j] = cr;
                }
            }
          }
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        // check bad inputs
        int n = board.size();
        int m = board[0].size();
        int w = words.size();
        if( w != 0 && n*m != 0){
            // Construct a trie with the content of the board  
            Trie trie;
            for(int k = 0; k < w; ++k){
                trie.insert(words[k]);
            } 
            
            // Search the board while comparing the read word to the trie content
            for(int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                {
                    findNextChar(i, j, 0, n, m, board, trie.root, w, res);
                }
            }   
        }  
        
        return res;
    }
    

    C# version

    class TrieNode {
            public string Value;
            public TrieNode[] Children;
            // Initialize your data structure here.
            public TrieNode() {
                Children = new TrieNode[26];
            }
        }
        
        class Trie {
            public TrieNode Root{ get; private set;}
        
            public Trie() {
                Root = new TrieNode();
            }
        
            // Inserts a word into the trie.
            public void Insert(String word) {
                TrieNode node = Root;
                int id;
                foreach (char cr in word)
                {
                  id = cr - 'a';
                  if (node.Children[id] == null){
                      node.Children[id] = new TrieNode();
                  }
                    
                  node = node.Children[id];
                }
        
                node.Value = word;
            }
        } 
        
        void FindNextChar(int i, int j, int offset, char[,] board, TrieNode node, int maxResults, IList<string> res){
            // Ensure that all the words are not found and i,j are within the board's boundary
            if (res.Count < maxResults && i >= 0 && j >= 0 && i < board.GetLength(0) && j < board.GetLength(1))
            {
                char cr = board[i, j];
                if (cr != '\0')
                {
                    int index = cr - 'a';
                    TrieNode child = node.Children[index];
                    if(child != null){
                        // flag the current character
                        board[i, j] = '\0';
                        if(!string.IsNullOrEmpty(child.Value)){
                            // We found a word, add it to the results
                            res.Add(child.Value);
                            // set the node value to empty string to avoid searching for it once again
                            child.Value = string.Empty;
                        }
                        
                        if(res.Count < maxResults){
                             // Search for next char (offset + 1) in neighborhood.
                            int newoffset = offset + 1;
                            FindNextChar(i + 1, j, newoffset, board, child, maxResults, res);
                            FindNextChar(i - 1, j, newoffset, board, child, maxResults, res);
                            FindNextChar(i, j + 1, newoffset, board, child, maxResults, res);
                            FindNextChar(i, j - 1, newoffset, board, child, maxResults, res); 
                        }
                        
                        // put back the current character value
                        board[i, j] = cr;
                    }
                }
              }
        }    
    
        public IList<string> FindWords(char[,] board, string[] words) {
            IList<string> res = new List<string>();
            // check bad inputs
            if(board == null || words == null || words.Length == 0) 
                return res;
            int n = board.GetLength(0);
            int m = board.GetLength(1);
            if(n == 0 && m == 0)
                return res;
            
            // Construct a trie with the content of the board  
            Trie trie = new Trie();
            foreach(string word in words){
                trie.Insert(word);
            }
            
            // Search the board while comparing the read word to the trie content
            for(int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                {
                    FindNextChar(i, j, 0, board, trie.Root, words.Length, res);
                }
            } 
    
            return res;        
        }

  • 0
    S

    newoffset and offset is not used..?


Log in to reply
 

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