矩阵路径--判断一个矩阵中是否存在一条包含某字符串所有字符的路径

  1 import java.util.ArrayList;
  2 import java.util.HashSet;
  3 import java.util.List;
  4 import java.util.Set;
  5 
  6 /**
  7  * 判断矩阵路径中是否包含某个字符串
  8  * @author zhangsw
  9  *
 10  */
 11 public class MatrixRoute2 {
 12     
 13     public static void main(String[] args) {
 14         char[][] charmatrix = {{‘a‘,‘b‘,‘c‘,‘e‘},
 15                                {‘s‘,‘f‘,‘c‘,‘s‘},
 16                                {‘a‘,‘d‘,‘e‘,‘e‘}};
 17         
 18         String string1 = "bfce";
 19         String string2 = "eecfs";
 20         String string3 = "adfccs";
 21         
 22         System.out.println(FindString(charmatrix, string1));
 23         System.out.println(FindString(charmatrix, string2));
 24         System.out.println(FindString(charmatrix, string3));
 25         
 26     }
 27     
 28     
 29     // 定义匹配成功后遍历该字符周围路径, 方向依次为左，右，下，上
 30     final static int[][] aroud = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
 31     
 32     // 定义一个存放已经过的矩阵中字符位置
 33     public static List<Integer[]> pathList = new ArrayList<Integer[]>();
 34     
 35     
 36     /**
 37      * 
 38      * @param charmatrix   字符数组
 39      * @param string       匹配的字符串
 40      * @return boolean
 41      */
 42     public static boolean FindString(char[][] charmatrix, String string) {
 43         
 44         for(int i=0; i<charmatrix.length; i++) {
 45             for(int j=0; j<charmatrix[0].length; j++) {
 46                 
 47                 if( findAroud(charmatrix, pathList, string, i, j)) {
 48                     return true;
 49                 }
 50 
 51             }
 52             
 53             
 54         }
 55         
 56         return false;
 57     }
 58     
 59     
 60     /**
 61      * 匹配到字符串首个字母之后开始查找该字符周围的字符串
 62      * @param charmatrix 传入的字符二维列表
 63      * @param string 被匹配的字符串
 64      * @param i matrix 的rows
 65      * @param j matrix 的clos
 66      * @return
 67      */
 68     public static boolean findAroud(char[][] charmatrix,List<Integer[]> pathList, String string, int i, int j) {
 69         // 字符串索引
 70         int stringIndex = 0;
 71         
 72         // 匹配到周围字符的标记
 73         boolean flag = false;
 74         
 75             // 若二维数组中某个字符匹配到字符串首字符，则开始在周围匹配下一个字符
 76             // 移动方向为上下左右，并且字符不能重复经过
 77             if (charmatrix[i][j] == string.charAt(stringIndex)) {
 78                 Integer[] posiInteger = {i,j};
 79                 pathList.add(posiInteger);
 80                 stringIndex++;
 81                 
 82                 // 遍历矩阵中该字符周围的数
 83                 while (stringIndex <= string.length()) {
 84                     
 85                     // 若字符索引 
 86                     if (stringIndex == string.length()) {
 87                         return true;
 88                     }
 89                     
 90                 
 91                     // 遍历周围字符
 92                      for (int[] item:aroud) {
 93                         i = i+item[0];
 94                         j = j+item[1];
 95                         Integer[] posiaround = {i,j};
 96                         
 97                         // 上下左右移动不能越界，且矩阵中该处索引未被经过
 98                         if (0<= i && i < charmatrix.length && 0 <= j && j < charmatrix[0].length && !pathList.contains(posiaround)) {
 99                             if    (string.charAt(stringIndex) == charmatrix[i][j]) {
100                                 
101                                 // 将该路径存入路径列表
102                                 pathList.add(posiaround);
103                                 // 字符串索引向后移动
104                                 stringIndex++;
105                                 
106                                 // 匹配到一个字符
107                                 flag = true;
108                                 break;
109                             }
110                             
111                         } 
112                         
113                         // 回到匹配字符的指针
114                         i = i-item[0];
115                         j = j-item[1];
116                         flag = false;
117                         
118                     }
119                      
120                      // 如果上下左右都匹配不到 返回false
121                      if (!flag) {
122                          return flag;
123                      }
124                 
125                 
126             }
127             
128             
129             }
130         
131         // 若字符矩阵中该字符不匹配字符串首字符或者字符串匹配过程中失败 返回false
132         return false;
133     }
134 
135 }