@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks
  • Offer (C++ version) series: Offer 10-i Fibonacci sequence
  • Sword finger Offer (C++ version) series: sword finger Offer 10-ii frog jump step problem
  • Finger Offer (C++ version) series: finger Offer 11 rotates the smallest number in the array

1, dry

The path in the matrix is 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). Example 1: input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED output:" true example 2: input: Board = [[" a ", "b"], [" c ", "d"]], the word = "abcd" output: false tip: 1 <= board. Length <= 200 1 <= board[I]. Length <= 200 https://leetcode-cn.com/problems/word-search/ 138,752 applications 305,361 submissionsCopy the code

Depth-first search

Depth-first search: Can be interpreted as a brute force method to traverse all string possibilities in a matrix. That is, DFS searches to the end in one direction through recursion, then goes back to the last node and searches in another direction, and so on until all searches are completed or stopped.

Prune: In the search, if this path is not successful, you should immediately return and abandon this node.

Algorithm flow:

  • Recursive parameters: row index I and column index J of the current character in the matrix board, and index K of the current target character (matched) in the target string Word.
  • Termination Conditions:
    • Returns false: (1) the row index or column index is out of bounds (2) the current matrix character is different from the target character;
    • Return true: the index of the current target character (matched) in the target string word k = len(word) -1, that is, the target string word has all matched;
  • Recursive process:
    • Mark accessed character: change board[I][j] to ‘/’ to indicate that this element has been accessed and prevent repeated access during subsequent searches.
    • Search for the next cell of the current character: turn on lower recursion up, down, left, and right of the current element, and record the result to the Boolean variable res.
    • Traceback current character: Restores the board[I][j] element to its initial value.
  • Return value: Returns the Boolean value res, which indicates whether the target string was searched.
// Interview question 12. Paths in a matrix
// Standard practice
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(a); i++) {for (int j = 0; j < board[0].size(a); j++) {if (dfs(board, word, i, j, 0))
                    return true; }}return false;
    }
    bool dfs(vector<vector<char>>& b, string& w, int i, int j, int k) {
        if (i >= b.size() || i < 0 || j >= b[0].size() || j < 0|| b[i][j] ! = w[k])return false;
        if (k == w.length() - 1)
            return true;
        char temp = b[i][j];
        b[i][j] = '/';
        bool res = dfs(b, w, i + 1, j, k + 1) | |dfs(b, w, i - 1, j, k + 1) | |dfs(b, w, i, j + 1, k + 1) | |dfs(b, w, i, j - 1, k + 1);
		/ * so to write, is better: int dx [4] = {1, 0, 1, 0}, dy [4] = {0, 1, 0, 1}; for (int q = 0; q < 4; q ++ ) { int m = i + dx[q], n = j + dy[q]; if (dfs(b, w, m, n, k + 1)) return true; } * /
        b[i][j] = temp;
        returnres; }};Copy the code

4. Complexity

/* Time complexity O(3^K MN) : in the worst case, we need to traverse all schemes of length K string in the matrix, time complexity is O(3^K); The matrix has MN starting points and the time complexity is O(MN). Space complexity O(K) : The depth of recursion in the search does not exceed K, so the stack space used by the system for function calls accumulates O(K) (because the stack space used by system calls is freed when the function returns). In the worst case, K=MN, the recursion depth is MN, and the system stack uses O(MN) extra space. * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks
  • Offer (C++ version) series: Offer 10-i Fibonacci sequence
  • Sword finger Offer (C++ version) series: sword finger Offer 10-ii frog jump step problem
  • Finger Offer (C++ version) series: finger Offer 11 rotates the smallest number in the array

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…