[help] work well locally, but got RE in a simple case


  • 0
    E

    got Runtime Error in case : ["a"], ["a"];

    this works well locally, I debugged step by step and cannot find the problem.

    at first, I didn't add the destructor; but it seems the destructor is not the point.

    class Trie{
    public:
      int MAX_N;
      static const int CLD_NUM = 26;
    
      int size;
      int *tag;
      int **trie;
    
      void reset();
      void insert(string s);
      bool search(string s);
      bool startsWith(string prefix);
      int find(string s);
      Trie(int max_n) : MAX_N(max_n) { reset(); }
      ~Trie() {
        delete[] tag;
        for (int i = 0; i < size; ++i) {
          delete[] trie[i];
        }
        delete[] trie;
      }
    };
    
    void Trie::reset(){
      tag = new int[MAX_N];
      trie = new int*[MAX_N];
      trie[0] = new int[CLD_NUM];
      memset(trie[0], -1, CLD_NUM * sizeof(int*));
      tag[0] = 0;
      size = 1;
    }
    
    void Trie::insert(string str){
      int p = 0;
      const char *s = &str[0];
      while (*s){
        int i = *s - 'a';
        if (-1 == trie[p][i]){
          trie[size] = new int[CLD_NUM];
          memset(trie[size], -1, CLD_NUM * sizeof(int*));
          tag[size] = 0;
          trie[p][i] = size++;
        }
        p = trie[p][i];
        ++s;
      }
      ++tag[p];
    }
    
    bool Trie::search(string str) {
      int p = find(str);
      if (p > 0 && tag[p] > 0 ) {
          tag[p] = -1;
          return true;
      }
      return false;
    }
    
    bool Trie::startsWith(string str) {
      int p = find(str);
      return p > 0;
    }
    
    int Trie::find(string str) {
      int p = 0;
      const char *s = &str[0];
      while (*s) {
        int i = *s - 'a';
        if (-1 == trie[p][i]) return -1;
        p = trie[p][i];
        ++s;
      }
      return p;
    }
    
    class Solution {
    public:
    void put(vector<string> &res, vector<vector<char>> &mat, vector<vector<bool>> &pos, int x, int y, string s, Trie &t) {
      if (pos[x][y]) return;
      s += mat[x][y];
      if (!t.startsWith(s)) return;
      if (t.search(s)) res.push_back(s);
    
      pos[x][y] = true;
      int n = mat.size(), m = mat[0].size();
      if (x > 0) put(res, mat, pos, x - 1, y, s, t);
      if (x < n - 1) put(res, mat, pos, x + 1, y, s, t);
      if (y > 0) put(res, mat, pos, x, y - 1, s, t);
      if (y < m - 1) put(res, mat, pos, x, y + 1, s, t);
    
      pos[x][y] = false;
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
      int n = board.size();
      vector<string> res;
      if (n == 0) return res;
      int m = board[0].size();
      if (m == 0) return res;
      int count = words.size();
      if (count == 0) return res;
      Trie t(count * 4);
      for (auto &i : words) {
        t.insert(i);
      }
      vector<vector<bool>> pos(n, vector<bool>(m, 0));
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          put(res, board, pos, i, j, "", t);
        }
      }
    
      return res;
    }
    
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.