LeetCode June Challenge - Day 30

Problem: LeetCode June Challenge - Day 30

Ideas

  1. Backtracking. I used recursion to make it easier to implement.
  2. I use the Trie I implemented for another daily task, with one modification, it now deletes a word after finding it, preventing me from pushing duplicates to the answer.

Solution:

class Node {
    private:
        Node* l['z'-'a'+1];
        bool end;
    public:
        Node(){
            end = false;
            memset(l,0,sizeof(l));
        }
        void mark(){
            end = true;
        }
        void unmark(){
            end = false;
        }
        bool is_marked(){
            return end;
        }
        Node* insert(char c){
            if(l[c-'a'] == NULL)
                l[c-'a'] = new Node();
            return l[c-'a'];
        }
        Node* get(char c){
            return l[c-'a'];
        }
};

class Trie {
    Node* root;
    public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string& word) {
        Node* it = root;
        for(char c : word){
            it = it->insert(c);
        }
        it->mark();
    }

    /** Returns if the word is in the trie. */
    bool search(string& word) {
        Node* it = root;
        for(char c : word){
            it = it->get(c);
            if(it == NULL) return false;
        }
        if(it->is_marked()){
            it->unmark();
            return true;
        }
        return false;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* it = root;
        for(char c : prefix){
            it = it->get(c);
            if(it == NULL) return false;
        }
        return true;
    }
};

class Solution {
    int n, m;
    Trie* t;
    string current;
    vector<string> ans;
    bool visited[30][30];

    void recursion(int i, int j, vector<vector<char>>& board){
        current.push_back(board[i][j]);
        if(t->startsWith(current)){
            if(t->search(current))
                ans.push_back(current);
            visited[i][j] = true;
            if(i > 0 && !visited[i-1][j])
                recursion(i-1, j, board);
            if(i < n-1 && !visited[i+1][j])
                recursion(i+1, j, board);
            if(j > 0 && !visited[i][j-1])
                recursion(i, j-1, board);
            if(j < m-1 && !visited[i][j+1])
                recursion(i, j+1, board);
            visited[i][j] = false;
        }
        current.pop_back();
    }

    public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.empty() || board[0].empty())
            return vector<string>();

        t = new Trie();
        memset(visited, 0, sizeof(visited));
        for(string s : words) t->insert(s);
        current = "";
        n = board.size(), m = board[0].size();

        for(int i=0; i<board.size(); ++i)
            for(int j=0; j<board[i].size(); ++j)
                recursion(i,j, board);
        return ans;
    }
};