9-矩阵中的路径

题目描述

请设计⼀个函数，⽤来判断在⼀个矩阵中是否存在⼀条包含某字符串所有字符的路径。路径可以从矩阵中的任意⼀个格⼦开始，每⼀步可以在矩阵中向左，向右，向上，向下移动⼀个格⼦。如果⼀条路径经过了矩阵中的某⼀个格⼦，则该路径不能再进⼊该格⼦。例如矩阵：

中包含⼀条字符串 " bcced " 的路径，但是矩阵中不包含 " abcb " 路径，因为字符串的第⼀个字符 b占据了矩阵中的第⼀⾏第⼆个格⼦之后，路径不能再次进⼊该格⼦。

示例1

输⼊：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值：true

思路及解答

主要的思路是对于每⼀个字符为起点，递归向四周拓展，然后遇到不匹配返回 false ，匹配则接着匹
配直到完成，⾥⾯包含了回溯的思想。步骤如下：

针对每⼀个字符为起点，初始化⼀个和矩阵⼀样⼤⼩的标识数组，标识该位置是否被访问过，⼀开始默认是false 。

如果当前的字符索引已经超过了字符串⻓度，说明前⾯已经完全匹配成功，直接返回 true
如果⾏索引和列索引，不在有效的范围内，或者改位置已经标识被访问，直接返回 false
否则将当前标识置为已经访问过
如果矩阵当前位置的字符和字符串相等，那么就字符串的索引加⼀，递归判断周边的四个，只要⼀个的结果为 true ，就返回 true ，否则将该位置置为没有访问过（相当于回溯，退回上⼀步），返回 false 。矩阵当前位置的字符和字符串不相等，否则同样也是将该位置置为没有访问过（相当于回溯，退回上⼀步），返回 false 。

⽐如查找 bcced :

import java.util.*;

public class Solution {
    public boolean hasPath(char[][] matrix, String word) {
        // write code here
        if (matrix == null || word == null || word.length() == 0) {
        	return false;
        }
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                boolean[][] flags = new boolean[matrix.length][matrix[0].length];
                
                boolean result = judge(i, j, matrix, flags, word, 0);
                if (result) {
                	return true;
                }
            }
        }
        return false;
   }
    
   public boolean judge(int i, int j, char[][] matrix, boolean[][] flags, String words, int index) {
        if (index >= words.length()) {
        	return true;
        }
       
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || flags[i][j]) {
        	return false;
        }
        flags[i][j] = true;
        
        if (matrix[i][j] == words.charAt(index)) {
            if (judge(i - 1, j, matrix, flags, words, index + 1)
            || judge(i + 1, j, matrix, flags, words, index + 1)
            || judge(i, j + 1, matrix, flags, words, index + 1)
            || judge(i, j - 1, matrix, flags, words, index + 1)) {
            	return true;
            } else {
                flags[i][j] = false;
                return false;
        	}
        } else {
            flags[i][j] = false;
            return false;
        }
    }
}

时间复杂度: 最坏的情况是将棋盘的每个位置都遍历⼀次，⽽每个位置除⾸字⺟外都不能⾛已经⾛过的位置，故四个⽅向只有三个⽅向可以选择，故时间复杂度为 O(mn*k3), m * n 是矩阵⼤⼩。
空间复杂度: 借助了额外的空间表示是否被访问过，空间复杂度为 O(m * n) 。

其实也有⼀种做法是直接在原来的矩阵上⽤特殊的字符表示已经访问过，⽽不需要额外的矩阵空间，这样空间复杂度更⼩，这⾥不再演示。