文档章节

Word Search Problem with Trie Solution

B
 BlueWoods
发布于 2015/05/19 13:16
字数 835
阅读 7
收藏 0

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].


通过检查每一个入口( 0 <= i < n | n = board.height, 0 <= j < m|board.width)开始的(通过上下左右)相连的字符串,是否和给定的字符串匹配,可以在O(n * m * max(length of word) * count(words))的时间里完成;但是,当我们检查某个连在一起的字符串的时候,如果该字符串不是任何一个给定字符串的前缀,那么就可以提前结束,从而提升效率;快速检查某个字符串是一组字符串(某个字符串)前缀的数据结构是Trie;

class TrieNode {
    private TrieNode[] children;
    private boolean end = false;
    // Initialize your data structure here.
    public TrieNode() {
        this.children = new TrieNode[26];
    }

    public void insert(char[] words, int i) {
        if (i >= words.length - 1) {
            this.end = true;
            return;
        }

        int j = i + 1;
        char nxt = words[j];
        TrieNode child = children[nxt - 'a'];
        if (child == null) {
            child = new TrieNode();
            children[nxt - 'a'] = child;
        }
        child.insert(words, j);
    }

    public boolean startsWith(char[] words, int i) {
        if(i >= words.length - 1) {
            return true;
        }
        int j = i + 1;
        char nxt = words[j];
        TrieNode child = children[nxt - 'a'];
        if(child == null) {
            return false;
        }
        return child.startsWith(words, j);
    }

    public boolean search(char[] words, int i) {
        if(i >= words.length - 1) {
            return this.end;
        }
        int j = i + 1;
        char nxt = words[j];
        TrieNode child = children[nxt - 'a'];
        if(child == null) {
            return false;
        }
        return child.search(words, j);
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        root.insert(word.toCharArray(), -1);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        return root.search(word.toCharArray(), -1);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return root.startsWith(prefix.toCharArray(), -1);
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("ab");
        System.out.println(trie.search("a"));
        System.out.println(trie.startsWith("a"));
    }
}

有了trie,再通过深度优先算法;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by senyuanwang on 15/5/19.
 */
public class Solution {

    static int[] dx = new int[]{-1, 0, 0, 1};
    static int[] dy = new int[]{0, -1, 1, 0};

    public static void visit(char[][] board, boolean[][] checked, int i, int j, Trie trie, String path, Set<String> result) {
        if (trie.search(path)) {
            result.add(path);
//            return;
        }

        if (!trie.startsWith(path)) {
            return;
        }

        for (int k = 0; k < 4; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && !checked[x][y]) {
                checked[x][y] = true;
                visit(board, checked, x, y, trie, path + board[x][y], result);
                checked[x][y] = false;
            }
        }
    }

    public static List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        boolean[][] checked = new boolean[board.length][board[0].length];
        Set<String> result = new HashSet<String>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                checked[i][j] = true;
                visit(board, checked, i, j, trie, "" + board[i][j], result);
                checked[i][j] = false;
            }
        }

        List<String> list = new ArrayList<String>(result.size());
        for (String str : result) {
            list.add(str);
        }
        return list;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'a', 'a'}, {'a', 'b'}};

        String[] words = {"aba", "baa", "bab", "aaab", "aaa", "aaaa", "aaba"};
        System.out.println(findWords(board, words));
    }
}

这里需要注意的一点是,当检查到生成的字符串满足要求(即与数组中的某个字符串匹配)时,不能结束查找,否则会丢掉结果。比如在上面用于测试的例子中, aaa和aaab都符合条件,aaa将会被先找到,如果返回了,aaab将会被丢掉;

© 著作权归作者所有

上一篇: cucumber 初探
B
粉丝 4
博文 39
码字总数 21286
作品 0
杭州
私信 提问
Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

2018/02/10
0
0
字典中的最长单词 Longest Word in Dictionary

问题: Given a list of strings representing an English Dictionary, find the longest word in that can be built one character at a time by other words in . If there is more than o......

叶枫啦啦
2018/01/17
21
0
实现前缀树 Implement Trie (Prefix Tree)

问题: Implement a trie with , , and methods. Note: You may assume that all inputs are consist of lowercase letters . 解决:https://www.cnblogs.com/grandyang/p/4491665.html 【题......

叶枫啦啦
2017/11/17
33
0
Leetcode 211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string co......

ShutLove
2017/11/24
0
0
js 中文分词

简单的中文分词

Jinl_bm
2016/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二)

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二) List 类型的操作 1、 向列表左侧添加数据 Long leftPush = redisTemplate.opsForList().leftPush("name", name); 2、 向列表右......

TcWong
今天
7
0
排序––快速排序(二)

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架: 1、首先需要设置一个枢轴元素即setPivot(int i); 2、然后需要与枢轴元素进行比较即int comparePivot(int j); 3、最后...

FAT_mt
昨天
4
0
mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
昨天
10
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
昨天
9
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部