leetcode212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

思路：上一道题改一下，把每一个单词都判断一下即可。

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 private boolean[][] marked;
     
    
   

    

     

    
    

     
 // x-1,y
     
    
   

    

     

    
    

     
 // x,y-1 x,y x,y+1
     
    
   

    

     

    
    

     
 // x+1,y
     
    
   

    

     

    
    

     
 private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
     
    
   

    

     

    
    

     
 // 盘面上有多少行
     
    
   

    

     

    
    

     
 private int m;
     
    
   

    

     

    
    

     
 // 盘面上有多少列
     
    
   

    

     

    
    

     
 private int n;
     
    
   

    

     

    
    

     
 private String word;
     
    
   

    

     

    
    

     
 private char[][] board;
     
    
   

    

     

    
    

     
 //答案数组
     
    
   

    

     

    
    

     

       Set<String> ans=new HashSet<>();
     
    
   

    

     

    
    

     
 //判断一个字符
     
    
   

    

     

    
    

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

    

     

    
    

     

       m = board.length;
     
    
   

    

     

    
    

     
 if (m == 0)return null;
     
    
   

    

     

    
    

     

       n = board[0].length;
     
    
   

    

     

    
    

     

       marked = new boolean[m][n];
     
    
   

    

     

    
    

     
 this.board = board;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for(String s:words){
     
    
   

    

     

    
    

     
 for (int i = 0; i < m; i++)
     
    
   

    

     

    
    

     
 for (int j = 0; j < n; j++)
     
    
   

    

     

    
    

     

       marked[i][j]=false;
     
    
   

    

     

    
    

     
 this.word = s;
     
    
   

    

     

    
    

     
 for (int i = 0; i < m; i++)
     
    
   

    

     

    
    

     
 for (int j = 0; j < n; j++)
     
    
   

    

     

    
    

     
 if (dfs(i, j, 0))
     
    
   

    

     

    
    

     

       ans.add(s);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       List<String> ansList=new ArrayList<>(ans);
     
    
   

    

     

    
    

     

       Collections.sort(ansList);
     
    
   

    

     

    
    

     
 return ansList;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 private boolean dfs(int i, int j, int start) {
     
    
   

    

     

    
    

     
 if (start == word.length() - 1) {
     
    
   

    

     

    
    

     
 return board[i][j] == word.charAt(start);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (board[i][j] == word.charAt(start)) {
     
    
   

    

     

    
    

     

       marked[i][j] = true;
     
    
   

    

     

    
    

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

    

     

    
    

     
 int newX = i + direction[k][0];
     
    
   

    

     

    
    

     
 int newY = j + direction[k][1];
     
    
   

    

     

    
    

     
 if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {
     
    
   

    

     

    
    

     
 if (dfs(newX, newY, start + 1)) {
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       marked[i][j] = false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104430212