This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

One, foreword

Hello, everyone. This article is the eighth article in the series of “Sword point Offer daily one”.

In this series of articles I will review the basics of data structures and algorithms by practicing brushing, and I will also share my brush history through a blog. Encourage each other to learn if you also plan to brush up on algorithms. The foundation of my algorithm is weak, and I hope to make up the loopholes in this area within two or three months. The brush language used this time is Java, and it is expected that the second brush will be completed in Python.

  • Brush topic platform: Leetcode’s Sword point Offer topic
  • Code cloud warehouse address

Second, the subject

Given an M x N 2d character grid board and a string word 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 contiguous horizontally or vertically. Letters in the same cell are not allowed to be reused.

For example, the following 3 by 4 matrix contains the word “ABCCED” (the letters in the word are indicated).

Example 1:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED" output: trueCopy the code

Example 2:

Input: board = [[" a ", "b"], [" c ", "d"]], the word = "abcd" output: falseCopy the code

Third, the problem solving

This is a classic problem that can be solved by backtracking.

Backtracking algorithms are actually search attempts similar to enumerations, one by one, as shown in the figure below.

And you can see that if you start at a point in the matrix and you go up, down, left, or right, that point could be any point in the matrix.

Stepwise recursion, you can think of it as a quadtree. So that’s the depth traversal.

From this diagram, the process for finding A->B->C->C->D looks like this:

  • 1, first find A point, then, traversing its “subtree”, that is, up, down, left and right, found that S can not go, so can only go B.
  • 2, find B, again, find his top, bottom, left and right four nodes, find C
  • 3, in turn, if not found, go back to the previous node to try to find, this is actually the application of recursion.

Note that if a point is accessed, we need to set it to accessed, otherwise an infinite loop may occur. It also marks the character as accessed to prevent the character from repeating the original character of the matrix. And, of course, once we get out of the recursion, we’re going to restore the character to its original value.

3.1 code

public class Number9 { public static void main(String[] args) { char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}; String word = "ABCCED"; System.out.println(exist(board,word)); } public static boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; If (DFS (board, words, I,j, 0)) return true; } } return false; } static Boolean DFS (char[][] board, char[] word, int I, int j, int index) { [I][j] = board[I][j] = board[I] Direct return false if (I > = board. Length | | I < 0 | | j > = board [0]. Length | | j < 0 | | board [I] [j]. = word[index]) return false; If (index == word. Length - 1) return true; if (index == word. Char TMP = board[I][j]; Board [I][j] = '#'; // Pass recursion, Along the direction of the current coordinates of the up and down or so four find Boolean res = DFS (board, a word, I + 1, j, index + 1) | | DFS (board, a word, I - 1, j, index + 1) || dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1); Board [I][j] = TMP; return res; }}Copy the code

3.2 Operation Effect

3.3 Complexity Analysis

  • Time complexity: the matrix has M*N points, and the time complexity is O (MN).
  • Space complexity: The stack space is used as the depth of recursion.

Four,

This topic examines the application of traceback in two-dimensional array, traceback is usually used to solve the maze problem, find the path, the topic also abstractly array into quadtree, to facilitate our understanding, traceback classic problem, must master.

Today’s brush topic to this, welcome to like comment exchange, sword point Offer brush topic journey will continue to unfold!