数据结构与算法--回朔，矩阵中查找字符串路径

喜欢ヅ旅行 2022-11-12 11:50 95阅读 0赞

package com.ljm.reversion;
    
    /** * Created by jiamin5 on 2021/3/23. */
    public class FindStrInMatrix { 
        public static void main(String[] args) { 
            char[][] chars = new char[4][4];
            String str = "abcd";
            
        }
    
        public static boolean findPath(char[][] arrays, int rows, int cols, String str){ 
            if(arrays == null || rows <=1 || cols <= 1 || str == null){ 
                return false;
            }
            boolean[][] visitArray = new boolean[rows][cols];
            int strLength = 0;
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    return isPath(arrays, rows, cols, i, j, str, visitArray, strLength);
                }
            }
            return false;
        }
    
        public static boolean isPath(char[][] arrays, int rows, int cols, int row, int col, String str, boolean[][] visitArray, int strLength){ 
            if(str.charAt(strLength)  == '\0'){ 
                return true;
            }
            boolean hasPath = false;
            if(row >= 0 && row <= rows && col >=0 && col < cols
                    && str.charAt(strLength) == arrays[row][col]
                    && visitArray[row][col] == false){ 
                strLength ++;
                visitArray[row][col] = true;
                hasPath = isPath(arrays, rows, cols, row,col+1, str, visitArray, strLength)
                        || isPath(arrays, rows, cols, row,col-1, str, visitArray, strLength)
                        || isPath(arrays, rows, cols, row+1,col, str, visitArray, strLength)
                        || isPath(arrays, rows, cols, row-1,col, str, visitArray, strLength);
                if(!hasPath){ 
                    strLength --;
                    visitArray[row][col] = false;
                }
            }
            return hasPath;
        }
    }