33ms c++ modular code


  • 0
    I

    standard trie + dfs, modular and easy to read

    struct trieNode
    {
    	bool isValid;
    	int idx;
    	trieNode *next[26];
    	trieNode(bool flag = false)
    	{
    		memset(next, 0, sizeof(next));
    		isValid = flag;
    		idx = 0;
    	}
    };
    
    class Trie: public trieNode
    {
    public:
    	trieNode *root;
    	Trie()
    	{
    		root = new trieNode;
    	}
    	void insert(string s, int idx)
    	{
    		trieNode *ptr = root;
    		for (int i = 0; i < s.size(); i++)
    		{
    			if (ptr->next[s[i] - 'a'] == NULL)
    			{
    				trieNode*temp = new trieNode;
    				ptr->next[s[i] - 'a'] = temp;
    			}
    			ptr = ptr->next[s[i] - 'a'];
    		}
    		ptr->isValid = true;
    		ptr->idx = idx;
    	}
    };
    
    class Solution :public Trie
    {
    public:
    	int dirs[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };
    	void insertWord(vector<string>&words)
    	{
    		for (int i = 0; i < words.size(); i++)
    		{
    			insert(words[i], i);
    		}
    	};
    	vector<string> findWords(vector<vector<char>>& board, vector<string>& words)
    	{
    		insertWord(words);
    		vector<string> rtn;
    		for (int i = 0; i < board.size(); i++)
    		{
    			for (int j = 0; j < board[0].size(); j++)
    			{
    				helper(i, j, board, words, rtn, root);
    			}
    		}
    		return rtn;
    	};
    
    	void helper(int i, int j, vector<vector<char>>& board, vector<string>& words, vector<string>& rtn, trieNode *ptr)
    	{
    		char placeholder = board[i][j];
    		if (board[i][j] == '0' || ptr->next[placeholder - 'a'] == NULL)
    			return;
    		if (ptr->next[placeholder - 'a']->isValid == true)
    		{
    			rtn.push_back(words[ptr->next[placeholder - 'a']->idx]);
    			ptr->next[placeholder - 'a']->isValid = false;
    		}
    		board[i][j] = '0';
    		for (int k = 0; k < 4; k++)
    		{
    			int ni = i + dirs[k][0];
    			int nj = j + dirs[k][1];
    			if (ni < board.size() && ni >= 0 && nj >= 0 && nj < board[0].size())
    			{
    				helper(ni, nj, board, words, rtn, ptr->next[placeholder - 'a']);
    			}
    		}
    		board[i][j] = placeholder;
    	};
    };
    

Log in to reply
 

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