単語検索Ⅱ
問題
直感: 単語配列内に存在する (グリッド/ボード上の) 単語を、上下左右に移動して見つけなければなりません。
トラバースはバックトラッキング
を使用して実行できます。
単語の検索には trie を利用できます。これは、接頭辞がツリー内に存在するかどうかを確認することで、早期の識別にも役立ちます。これは、ボードの不必要な走査を避けるためです(つまり、ボードを走査しても意味がありません。接頭辞がトライに存在しない場合、その接頭辞を使用する文字列または単語形式もトライに存在しません)
アプローチ: すべての単語 [] をトライに配置します。次に、各セル (i,j) についてボードを横断し、4 方向すべてに進み、さまざまな文字列を形成します。リスト内のトライに存在する文字列。
class Solution { public List<String> findWords(char[][] board, String[] words) { int max = 0; Trie t = new Trie(); for (String w : words) { t.insert(w); } int arr[][] = new int[board.length][board[0].length]; StringBuilder str = new StringBuilder(); Set<String> list = new HashSet<>();// to have only unique strings/words for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { // recursively traverse all the cells to find the words traverse(i, j, board, arr, arr.length, arr[0].length, t, str, list); } } return new ArrayList<>(list); } public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set<String> list) { str.append(b[i][j]);// add current cell character to form a potential prefix/word if (!t.startWith(str.toString())) {//early checking of prefix before moving forward to avoid un-necessary traversal str.deleteCharAt(str.length() - 1); return; } if (t.present(str.toString())) list.add(str.toString()); arr[i][j] = 1;// mark current cell visited to avoid visiting the same cell the current recursive call stack int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };// left,right,up,down for (int dir[] : dirs) { int I = i + dir[0]; int J = j + dir[1]; if (I < n && J < m && I >= 0 && J >= 0 && arr[I][J] == 0) { traverse(I, J, b, arr, n, m, t, str, list); } } arr[i][j] =0;// mark unvisited str.deleteCharAt(str.length()-1);// remove the last added character } } class Node { Node node[] = new Node[26]; boolean flag; public boolean isPresent(char c) { return node[c - 'a'] != null; } public Node get(char c) { return node[c - 'a']; } public void add(char c, Node n) { node[c - 'a'] = n; } public void setFlag() { this.flag = true; } public boolean getFlag() { return this.flag; } } class Trie { Node root; public Trie() { root = new Node(); } public void insert(String s) { Node node = root; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!node.isPresent(c)) { node.add(c, new Node()); } node = node.get(c); } node.setFlag(); } public boolean present(String s) { Node node = root; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!node.isPresent(c)) { return false; } node = node.get(c); } return node.getFlag(); } public boolean startWith(String s) { Node node = root; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!node.isPresent(c)) { return false; } node = node.get(c); } return true; } }
以上が単語検索Ⅱの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











一部のアプリケーションが適切に機能しないようにする会社のセキュリティソフトウェアのトラブルシューティングとソリューション。多くの企業は、内部ネットワークセキュリティを確保するためにセキュリティソフトウェアを展開します。 ...

多くのアプリケーションシナリオでソートを実装するために名前を数値に変換するソリューションでは、ユーザーはグループ、特に1つでソートする必要がある場合があります...

システムドッキングでのフィールドマッピング処理は、システムドッキングを実行する際に難しい問題に遭遇することがよくあります。システムのインターフェイスフィールドを効果的にマッピングする方法A ...

intellijideaultimatiateバージョンを使用してスプリングを開始します...

データベース操作にMyBatis-Plusまたはその他のORMフレームワークを使用する場合、エンティティクラスの属性名に基づいてクエリ条件を構築する必要があることがよくあります。あなたが毎回手動で...

Javaオブジェクトと配列の変換:リスクの詳細な議論と鋳造タイプ変換の正しい方法多くのJava初心者は、オブジェクトのアレイへの変換に遭遇します...

eコマースプラットフォーム上のSKUおよびSPUテーブルの設計の詳細な説明この記事では、eコマースプラットフォームでのSKUとSPUのデータベース設計の問題、特にユーザー定義の販売を扱う方法について説明します。

Redisキャッシュソリューションは、製品ランキングリストの要件をどのように実現しますか?開発プロセス中に、多くの場合、ランキングの要件に対処する必要があります。
