The solution to the timeout of question 79 of Code Review: leetcode.

https://leetcode.com/problems.

my idea is to violently match the first letter, and then match the remaining letters up and down like a gluttonous snake, while using a vector k plus a Hash to convert the coordinates to a unique ID, to record the path. If you have already passed, the match does not pass.

after writing, I feel that this way of writing is wrong, and it should be quite different from the correct way of thinking. I don"t want to look at the answer directly, so I hope to get a hint of pointing out the shortcomings of the code and the right way of thinking. 

-sharpdefine HashP(A, B) A <<16 | B

inline bool goTo(int& i, int& j, int& n, int& m, vector<int> k,
          vector<vector<char>>& board, string& word){
    k.push_back(HashP(i, j));
    if(k.size() == word.size())
        return true;
    bool g1 = false, g2 = false, g3 = false, g4 = false;

    int next = i - 1;
    if(next >= 0 && board[next][j] == word[k.size()]
    && find(k.begin(), k.end(), HashP(next, j)) == k.end())
        g1 = goTo(next, j, n, m, k, board, word);

    next = i + 1;
    if(next < n  && board[next][j] == word[k.size()]
    && find(k.begin(), k.end(), HashP(next, j)) == k.end())
        g2 = goTo(next, j, n, m, k, board, word);

    next = j - 1;
    if(next >= 0 && board[i][next] == word[k.size()]
    && find(k.begin(), k.end(), HashP(i, next)) == k.end())
        g3 = goTo(i, next, n, m, k, board, word);

    next = j + 1;
    if(next < m && board[i][next] == word[k.size()]
    && find(k.begin(), k.end(), HashP(i, next)) == k.end())
        g4 = goTo(i, next, n, m, k, board, word);
    return g1 || g2 || g3 || g4;
}

bool exist(vector<vector<char>>& board, string word) {
    int i,j;
    int n = board.size(), m = board[0].size();
    // if(word.size() > n * m) {
    //     return false;
    // }
    for(i = 0; i < n; iPP) {
        for(j = 0; j < m; jPP) {
            if(word.front() == board[i][j]) {
                vector<int> k;
                if(goTo(i, j, n, m, k, board, word)) {
                    return true;
                }
            }
        }
    }
    return false;
}

Update:

The problem with

timeout is that I wait for the result g1gramme to all return , and I should immediately return when a result is true . Thank you @ Caocong for your answer

CPP algorithm optimization
Jul.24,2021

I wrote it in js. I don't know how different it is from cPP.
the basic idea is gluttonous, but I generated an object to store the coordinates of each letter
, which is faster than traversing the path once at a time

. 
var exist = function (board, word) {
  const initial = word[0]
  const rest = word.substring(1, word.length)
  let flag = false
  let boardarr = {}
  for (let i = 0; i < board.length; iPP) {
    for (let j = 0; j < board[i].length; jPP) {
      boardarr[board[i][j]] = boardarr[board[i][j]] || []
      boardarr[board[i][j]].push([i, j])
    }
  }
  if (boardarr[initial]) {
    for (let i = 0; i < boardarr[initial].length; iPP) {
      f([[boardarr[initial][i][0], boardarr[initial][i][1]]], rest, {
        ...boardarr,
        [initial]: boardarr[initial].filter(val => !(val[0] === boardarr[initial][i][0] && val[1] === boardarr[initial][i][1]))
      })
      if (flag)
        return flag
    }
  }

  function f (path, word, barr) {
    if (!flag) {
      if (word.length) {
        const initial = word[0]
        const rest = word.substring(1, word.length)
        if (barr[initial]) {
          for (let i = 0; i < barr[initial].length; iPP) {
            if ((path[0][0] === barr[initial][i][0] && Math.abs(path[0][1] - barr[initial][i][1]) === 1) || (path[0][1] === barr[initial][i][1] && Math.abs(path[0][0] - barr[initial][i][0]) === 1)) {
              f([barr[initial][i], ...path], rest, {
                ...barr,
                [initial]: barr[initial].filter(val => !(val[0] === barr[initial][i][0] && val[1] === barr[initial][i][1]))
              })
            }
          }
        }
      } else {
        flag = true
      }
    }
  }

  return flag
}

Previous: There is no response after hexo modifies the theme file and then submits it.

Next: What are the ways to upload and download pictures or files?

css mysql arrays josn react html typescript webpack npm sass R objective-c .net sql-server jquery python-3.x angularjs django angular excel regex iphone ajax linux xml pandas vba spring database wordpress string wpf xcode windows bash postgresql oracle multithreading eclipse list firebase algorithm macos forms image scala visual-studio azure bootstrap spring-boot react-native python-2.7 docker performance function winforms matlab powershell apache dataframe api sqlite numpy rest shell selenium flutter dart maven loops qt swing android-studio csv express file class tensorflow sorting codeigniter perl
© 2021 CodesHelper
Advertising Contact us About us
Menu