preface

Given a matrix and a string, how do I find the path of the string in the matrix from the matrix? This article will share with you how to use backtracking to solve this problem. Interested developers are welcome to read this article.

Implementation approach

Let’s start with the condition given by the problem, and gradually analyze the idea that a matrix is a two-dimensional array, a string can be cut into an array, and what we need to do is to take each character in the string in order, and determine whether it is in the matrix, and whether it can form a complete path out.

Example analysis

We have a matrix (shown below) with a string bfce, and we need to find the concatenated path of the string in the matrix from the matrix.

a  b  t  g
c  f  c  s
j  d  e  h
Copy the code

We start from the [0][0] position of the matrix as the entry point. The first character to look for is b:

  • The 0,0 element is 0a, does not match the target value, continue looking for position 0,1
  • The element in position 0,1 is yesbMatches the target value, and the search continues for the second characterf
    • Update search direction, look down
  • The element in position 1,1 isf, matches the target value, and the search continues for the third characterc
    • Update search direction, look down
  • The element in position 2,1 isd, does not match the target value, return to the previous step 1,1 position
    • Update look for directions, look up,
    • We’ve already looked for the value of 0,0, so let’s go back to step 1,1
    • Update search direction, look right
  • The element at position 1,2 isc, matches the target value, and the search continues for the fourth charactere
    • Update search direction, look down
  • The element in position 2,2 ise, matches the target value, all characters are found, and the path exists in the matrix

Stores the index of the element found in each step in the matrix

  • [2]location
  • [1, 2]location
  • [1, 1]location
  • [0, 1]location

The final path is: [0][1], [1][1], [1][2], [2][2]

Thought analysis

Through the above examples, we can conclude the following ideas:

  • Look for a pointcut, starting with the first character and finding its position in the matrix
  • After entering the matrix, each step has four moving directions: down, up, right, and left
  • Each move determines whether the value of the moved position is equal to the character you are currently looking for
    • If they are, the element that identifies the current position is in the accessed state, and the search for the next character continues along the four moving directions
    • If not, it goes back to the previous position and tries to see if there are any matching elements in the other three directions
  • Repeat step 3 until all four directions of matched characters are moved
    • Once all the characters in the string are found, the correct index position for each step is retrieved and saved
    • If no element matching the character is found after all four directions are moved, the string does not exist in the matrix

Note: After we find an element in the matrix that matches the target character, we need to store the element at this position and then change to. Use to indicate that the element has been accessed and restore the stored value when all elements are found.

The implementation code

Now that we’ve figured out the idea, let’s look at the implementation code, which is divided into two parts:

  • The main function, which is used for parameter rule judgment, finding pointcuts, and returning the path found
  • The find path function, used to find each character in the matrix

The main function

The main function takes two arguments: the path matrix and the destination string

  • We need to null the parameters first
  • Iterating the matrix from0, 0Location begins to find the path
  • If the path is found, return the path index, otherwise return that the target path does not exist

Code implementation is as follows:

export default class Backtracking {
  // The index of the target path in the matrix
  private readonly pathIndex: Array<string>;

  constructor() {
    this.pathIndex = [];
  }
  
  public findMatrixPath(
    matrix: Array<Array<string>>,
    target: string) :Array<string> {
    if (target === "") {
      this.pathIndex.push("Parameter error: target path is empty");
      return this.pathIndex;
    }
    for (let i = 0; i < matrix.length; i++) {
      for (let j = 0; j < matrix[i].length; j++) {
        if (this.findPath(matrix, target, i, j, 0)) {
          return this.pathIndex; }}}/ / was not found
    this.pathIndex.push("The target path does not exist in the matrix");
    return this.pathIndex; }}Copy the code

Path finding function

The find path function takes five arguments: the path matrix, the target string, the row to find, the column to find, and the character index to find

  • First, we need to determine whether the rows and columns we’re looking for are beyond the bounds of the matrix
  • If the element in the position of the row or column in the matrix is not equal to the character in the matrixfalse
  • Determines whether all characters have been looked up
    • Return true if the index of the row and column is stored
    • If not, save the value at the current row or column and change the value to.Used to identify the state as accessed
  • From the current coordinate point position along its four directions: down, up, right, down search
  • After the search is complete, save the coordinates of the found characters and restore the value saved at the current position

Code implementation is as follows:

  private findPath(
    matrix: Array<Array<string>>,
    target: string.row: number.col: number.index: number) :boolean {
    // Boundary condition judgment
    // 1. Return false if the row or column value is out of bounds
    // 2. Matrix [row][col] position element is not the same as the character you are looking for
    if (
      row >= matrix.length ||
      row < 0 ||
      col >= matrix[0].length ||
      col < 0|| matrix[row][col] ! = target[index] ) {return false;
    }
    // All characters have been found
    if (index === target.length - 1) {
      // Store the coordinates of the last character in the matrix
      this.pathIndex.unshift(` [${row}] [${col}] `);
      return true;
    }
    // Save the current coordinate value
    const tmp = matrix[row][col];
    // Change the value of the current coordinate to indicate that the current coordinate point has been found
    matrix[row][col] = ".";
    // Start recursion: search in four directions along the current coordinate
    const res: boolean =
      this.findPath(matrix, target, row + 1, col, index + 1) | |this.findPath(matrix, target, row - 1, col, index + 1) | |this.findPath(matrix, target, row, col + 1, index + 1) | |this.findPath(matrix, target, row, col - 1, index + 1);
    // The current round of recursion is complete, finding the position of the character in the matrix
    if (res) {
      // Save the current coordinate point of the character to look for
      this.pathIndex.unshift(` [${row}] [${col}] `);
    }
    // Restore the current coordinate
    matrix[row][col] = tmp;
    return res;
  }
Copy the code

For the full code, go to backtracking.ts

Write test cases

Next, let’s plug the above example into the function we implemented to see if it works.

import Backtracking from ".. /Backtracking.ts";

const pathArr = [
  ["a"."b"."t"."g"],
  ["c"."f"."c"."s"],
  ["j"."d"."e"."h"]].const target = "bfce";
const backtracking = new Backtracking();
const findResult = backtracking.findMatrixPath(pathArr, target);
console.log(`${target}The path index in the matrix is', findResult);

Copy the code

The execution result is as follows:

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please go to my personal website to learn more.

  • Feel free to correct any mistakes in the comments section, and if this post helped you, feel free to like and follow 😊
  • This article was originally published in Nuggets and cannot be reproduced without permission at 💌