LeetCode 212. 単語検索II辞書ツリー遡及C++

説明
2 Dメッシュboardと辞書の単語リストwordsを指定し、2 Dメッシュと辞書に同時に表示されるすべての単語を見つけます.
単語はアルファベット順で、隣接するセル内のアルファベットで構成され、「隣接」セルは水平または垂直に隣接するセルである必要があります.同じセル内のアルファベットは、1つの単語で繰り返し使用できません.
例:
入力:words=["oath","pea","eat","rain"]and board=[‘o’,‘a’,‘n’],[‘e’,‘t’,‘a’,‘e’,[‘i’,‘h’,‘k’,‘r’],[‘i’,‘f’,‘l’,‘v’]
出力:[「eat」、「oath」]説明:すべての入力が小文字a-zで構成されていると仮定できます.
ヒント:
より大きなデータ量のテストに合格するために、遡及アルゴリズムを最適化する必要があります.早く遡及を止めてもらえますか?現在の単語がすべての単語の接頭辞に存在しない場合は、すぐに遡及を停止できます.どのようなデータ構造がこのような操作を効果的に実行できますか?ハッシュは実行できますか?どうして?接頭辞ツリーはどうですか?基本的な接頭辞ツリーの実装方法を学びたい場合は、Trie(接頭辞ツリー)の実装を確認してください.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/word-search-ii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
ぶんせき
辞書ツリーを使用するとwordsの単語を辞書ツリーに構成し、boardで順番に探すことができることをヒントにしました.boardの現在のアルファベットが辞書ツリーrootの下の分岐にある限り、再帰的に探すことができます.途中で辞書ツリーが歩けなくなったら戻り、すでに存在している単語が追加されます(ただし、返さない.aaaは、aaabも可能です).4つの方向で探して、利用可能なものを見つけたら、下に戻り続けます.
コード#コード#

class Solution {
public:
	struct Node {
		bool isflag = false;
		Node * next[27] = {};
	};
	setres; //       ，        
	vectorans;
	Node * root;
	vectordirx{ 0,0,1,-1 };
	vectordiry{ 1,-1,0,0 };
	bool flag;
	//     
	void createtree(vector&words) {
		root = new Node();
		
		for (auto w : words) {
			Node * p = root;
			for (int i = 0; i < w.length(); i++) {
				if (p->next[w[i] - 'a'] == NULL) {
					p->next[w[i] - 'a'] = new Node();
				}
				p = p->next[w[i] - 'a'];
			}
			p->isflag = true;
		}
	}
	void backtrack(vector>&board,vector>visited, int row, int col, Node*roott, string cur) {
		cur += board[row][col];
		roott = roott->next[board[row][col] - 'a'];
		if (!roott)return; //     
		if (roott->isflag == true)
		{
			//ans.push_back(cur);
			res.insert(cur);
			flag = true;
			//return;
		}
		visited[row][col] = true;
		
		for (int i = 0; i < 4; i++) {
			//if (flag == true)
				//return;
			int nx = row + dirx[i];
			int ny = col + diry[i];
			if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size())
				continue;
			if (visited[nx][ny] == false) {
				backtrack(board, visited, nx, ny, roott, cur);
				//visited[nx][ny] = false;
				//cur.pop_back();
			}
		}
		
	}
	vector findWords(vector>& board, vector& words) {
		
		if (board.size() == 0 || words.size() == 0)
			return ans;
		createtree(words);
		
		for (int i = 0; i < board.size(); i++) {
			for (int j = 0; j < board[i].size(); j++) {
				Node * p = root; //        root     
				flag = false;
				if (p->next[board[i][j] - 'a']) {
					vector>visited{ board.size(),vector(board[0].size(),false) };
					backtrack(board, visited, i, j, p, "");
				}
			}
		}
		set::iterator it;
		for (it = res.begin(); it != res.end(); it++)
			ans.push_back(*it);
		return ans;
	}
};