Code Review: leetcode 79题超时 解决办法。

Question

https://leetcode.com/problems...

我思路就是暴力匹配第一个字母，然后类似贪吃蛇一样上下左右把剩下的字母匹配了，同时用一个vector k加上一个Hash把坐标转换为唯一的ID，来记录走过的路径，如果已经走过则匹配不通过。

写完感觉这写法不对，应该和正确思路差别比较大。不想直接看答案，所以借此希望能得到指出代码的不足之处，和正确思路的提示。

#define 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; i++) {
        for(j = 0; j < m; j++) {
            if(word.front() == board[i][j]) {
                vector<int> k;
                if(goTo(i, j, n, m, k, board, word)) {
                    return true;
                }
            }
        }
    }
    return false;
}

Update:

超时的问题在于我等待结果g1,g2,g3,g4全部都走完才return,应该一个结果走通为true就立马return. 感谢 @草从 的回答

Answer 1

我是用js写的 不知道和c++实现有多大差异性
基本思路也是贪吃蛇 但我生成了个对象把每个字母的坐标存了进去
这个比每次遍历一次走过的路径要快些

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; i++) {
    for (let j = 0; j < board[i].length; j++) {
      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; i++) {
      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; i++) {
            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
}