Java实现 LeetCode 212 单词搜索 II

public class Find2 {

    public int[] dx={1,-1,0,0};

    public int[] dy={0,0,1,-1};

    class Trie{

        Trie[] tries;

        String isEnd;

        public Trie(){

            tries = new Trie[26];

        }

    }

    public boolean[][] vis;    //是否判断过

    public List<String> res;    //答案

    public void insert(String word, Trie root){

        Trie t = root;

        for(int i = 0;i < word.length();i++){

            int index = word.charAt(i)-'a';

            if(t.tries[index] == null){

                t.tries[index] = new Trie();

            }

            t = t.tries[index];//跳到子节点

        }

        t.isEnd = word;

    }

    public List<String> findWords(char[][] board, String[] words) {

        //先把单词存入字典树当中

        Trie root=new Trie();

        for(String word:words){

           insert(word,root);

        }

        res=new ArrayList<String>();

        vis=new boolean[board.length][board[0].length];

        for(int i=0;i<board.length;++i){  //对board每一个点都进行检索

            for(int j=0;j<board[i].length;++j){

                dfs(root,i,j,board);

            }

        }

        Collections.sort(res);  //需要对结果进行排序

        return new ArrayList<String>(res);

    }

    public void dfs(Trie cur,int x,int y,char[][] board){

        //判断边界

        if(x<0||y<0||x>=board.length||y>=board[0].length||vis[x][y]){

            return;

        }

        cur=cur.tries[board[x][y]-'a'];  //延伸下一个节点

        vis[x][y]=true; //把当前设置为走过 不可重复走

        if(cur!=null){ //如果当前不为null的话 可以继续检索

            if(cur.tries!=null){ //说明到这里已经可以组成一个单词了

                res.add(cur.isEnd);

                cur.tries=null; //变成null是为了防止重复加入单词

            }

            for(int i=0;i<4;++i){

                dfs(cur,x+dx[i],y+dy[i],board); //四个方向检索

            }

        }

        vis[x][y]=false;

    }

    public static void main(String[] args) {

        String[] words ={"oath","pea","eat","rain"};

        char[][] board = {

                {'o', 'a', 'a', 'n'},

                {'e', 't', 'a', 'e'},

                {'i', 'h', 'k', 'r'},

                {'i', 'f', 'l', 'v'}

        };

        Solution m = new Solution();

        List<String> a = m.findWords(board,words);

        System.out.println(a.toString());

    }

}
巴特西

Java实现 LeetCode 212 单词搜索 II

最新文章

热门文章
