《剑指Offer》回溯法

回溯法

通常物体或人在二维方格运动这类问题都可以用回溯法解决，一般把矩阵看成二维数组。

面试题

题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

solution
运行时间：35ms， 占用内存：5756k

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        self.col, self.row = cols, rows
        matrix = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == path[0]:
                    self.b = False
                    self.search(matrix, path[1:],[(i,j)],i,j)
                    if self.b:
                        return True
        return False

    def search(self, board, word, dict, i,j):
        if word == "":
            self.b = True
            return

        if j !=0 and (i,j-1) not in dict and board[i][j-1] == word[0]:
            self.search(board,word[1:],dict + [(i,j-1)],i,j-1)
        if i != 0 and (i - 1, j) not in dict and board[i - 1][j] == word[0]:
            self.search(board, word[1:], dict + [(i - 1, j)], i - 1, j)
        if j != self.col - 1 and (i, j + 1) not in dict and board[i][j + 1] == word[0]:
            self.search(board, word[1:], dict + [(i, j + 1)], i, j + 1)
        if i != self.row - 1 and (i + 1, j) not in dict and board[i + 1][j] == word[0]:
            self.search(board, word[1:], dict + [(i + 1, j)], i + 1, j)