単語検索Ⅱ

Sep 25, 2024 am 06:15 AM

Word Search II

問題

直感: 単語配列内に存在する (グリッド/ボード上の) 単語を、上下左右に移動して見つけなければなりません。
トラバースはバックトラッキング
を使用して実行できます。 単語の検索には 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットな記事タグ

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか? Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか? Mar 17, 2025 pm 05:35 PM

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?

高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか? 高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか? Mar 17, 2025 pm 05:46 PM

高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?

2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、Svelte 2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、Svelte Mar 07, 2025 pm 06:09 PM

2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、Svelte

Javaで機能的なプログラミング技術を実装するにはどうすればよいですか? Javaで機能的なプログラミング技術を実装するにはどうすればよいですか? Mar 11, 2025 pm 05:51 PM

Javaで機能的なプログラミング技術を実装するにはどうすればよいですか?

node.js 20:キーパフォーマンスが向上し、新機能 node.js 20:キーパフォーマンスが向上し、新機能 Mar 07, 2025 pm 06:12 PM

node.js 20:キーパフォーマンスが向上し、新機能

Iceberg:データレイクテーブルの未来 Iceberg:データレイクテーブルの未来 Mar 07, 2025 pm 06:31 PM

Iceberg:データレイクテーブルの未来

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか? キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか? Mar 17, 2025 pm 05:43 PM

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか? カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか? Mar 17, 2025 pm 05:44 PM

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?

See all articles