12. Path in matrix (backtracking > 100%)

First, retrospective method

Backtracking can be seen as an improved version of brute force, which systematically selects a viable solution from all possible options at each step of the problem. Backtracking is great for problems that consist of multiple steps, with multiple options for each step. When we select one of the options at a given step, we move on to the next step and then face a new choice. We do this repeatedly until we reach the final state.

All options for problems solved by backtracking can be represented graphically in a tree structure. If there are n possible options in a given step, the step can be viewed as a node in the tree structure, and each option can be viewed as a line of nodes in the tree, through which to reach the node’s N child nodes. The leaves of the tree correspond to terminal states.

Process:

• If the state of the leaf node satisfies the subleness condition of the problem, then we have found a feasible solution.

• If the state of the leaf node does not satisfy the constraint, then it has to go back to its previous node and try another option.

• If at the last node, all possible options have been tried and the final state that satisfies the condition cannot be reached, then the previous node is backtracked again.

• If all options on all nodes have been tried and still cannot reach the terminal state that satisfies the constraint, there is no solution.

Two, typical topics

Given an M x N two-dimensional character grid board and a string word. Return true if Word exists in the grid; Otherwise, return false.

Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused. For example, the 3×4 matrix below contains the word “ABCCED” (the letters in the word are highlighted).

|A|B|C|E|
|S|F|C|S|
|A|D|E|E|
Copy the code

Example 1:

Enter: board = [["A"."B"."C"."E"], ["S"."F"."C"."S"], ["A"."D"."E"."E"]], word = "ABCCED"Output:true
Copy the code

Example 2:

Enter: board = [["a"."b"], ["c"."d"]], word = "abcd"Output:false
Copy the code

Tip:

1 <= board.length <= 200
1 <= board[i].length <= 200Board and Word consist only of uppercase and lowercase English lettersCopy the code

Note: leetcode-cn.com/problems/wo…

Source: LeetCode link: leetcode-cn.com/problems/ju… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Third, solution

⭐ making

 func exist(_ board: [[Character]], _ word: String) -> Bool {
    let maxY = board.count
    let chars: [Character] = Array(word)
    
    guard let maxX = board.first?.count, maxY > 0, maxX > 0 else {
        return false
    }
    
    // Used to save access status
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: maxX), count: maxY)
    
    var pathLength = 0
    
    for y in 0..<maxY {
        for x in 0..<maxX {
            if hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y, visted: &visited) {
                return true}}}return false
}

func hasPathCore(_ board: [[Character]], _ chars: [Character].maxX: Int.maxY: Int.pathLength: inout Int.x: Int.y: Int.visted: inout [[Bool]]) -> Bool {
    if pathLength = = chars.count {
        return true
    }
    
    var result = false
    if x > = 0, y > = 0,
       x < maxX, y < maxY,
       visted[y][x] = = false,
       board[y][x] = = chars[pathLength]
    {
        pathLength + = 1
        visted[y][x] = true
        
        result =
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x - 1, y: y, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x + 1, y: y, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y - 1, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y + 1, visted: &visted)
        
        if result = = false {
            pathLength - = 1
            visted[y][x] = false}}return result
}

Copy the code

4

• Examine the understanding of backtracking. In general, finding a path on a two-dimensional matrix can be done by backtracking
• Test your ability to program arrays. We tend to think of matrices as two-dimensional arrays of nursery rhymes. Only with a full understanding of the properties of arrays can the code of backtracking be implemented quickly and correctly.

👋

• 📦 Archive technical documentation
• 🐙 making
• Wechat: RyukieW

My apps