Why my two versions of code so slow One TLE and One inefficient.


  • 0
    J

    Hi all, I use DFS for this problem, but the time efficiency is too low. In the version one I used unordered_set, which is equivalent to HashSet in Java, to check if a cell has been used for matching. The code can pass all tests, but only fall in the bottom 10% in time efficiency. The user defined stack rather than recursion stack is used in my code.

    #include <unordered_set>
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if (word=="")
                return true;
            int M = board.size(), N = board[0].size(), L = word.length();
            int temp_i, temp_j, dir, l;
            const int up=0, left=1, down=2, right=3, gone=4;
            if ((M*N==0)||(M*N<L))
                return false;
            stack<pair<int,int> > st;
            unordered_set<int> forbidden;
            // first = i*N+j, second = direction;
            // 0: up, 1: left, 2: down, 3: right
            for (int i=0; i<M; i++)
                for (int j=0; j<N; j++)
                {
                    if (board[i][j]==word[0])
                    {
                        if (L==1)
                            return true;
                        st.push(make_pair(i*N+j,up));
                        forbidden.insert(i*N+j);
                        while (!st.empty())
                        {
                            if (forbidden.size()==L)
                                return true;
                            temp_i = st.top().first; dir = st.top().second;
                            temp_j = temp_i%N; temp_i /= N;
                            if (dir==up)  // to check up
                            {
                                st.pop();
                                st.push(make_pair(temp_i*N+temp_j,right));
                                if ((temp_i==0)||(forbidden.count((temp_i-1)*N+temp_j)==1)||(board[temp_i-1][temp_j]!=word[forbidden.size()]))
                                    continue;
                                forbidden.insert((temp_i-1)*N+temp_j);
                                st.push(make_pair((temp_i-1)*N+temp_j,up));
                                continue;
                            }
                            if (dir==right)
                            {
                                st.pop();
                                st.push(make_pair(temp_i*N+temp_j,down));
                                if ((temp_j==N-1)||(forbidden.count(temp_i*N+temp_j+1)==1)||(board[temp_i][temp_j+1]!=word[forbidden.size()]))
                                    continue;
                                forbidden.insert(temp_i*N+temp_j+1);
                                st.push(make_pair(temp_i*N+temp_j+1,up));
                            }
                            if (dir==down)  // to check up
                            {
                                st.pop();
                                st.push(make_pair(temp_i*N+temp_j,left));
                                if ((temp_i==M-1)||(forbidden.count((temp_i+1)*N+temp_j)==1)||(board[temp_i+1][temp_j]!=word[forbidden.size()]))
                                    continue;
                                forbidden.insert((temp_i+1)*N+temp_j);
                                st.push(make_pair((temp_i+1)*N+temp_j,right));
                                continue;
                            }
                            if (dir==left)
                            {
                                st.pop();
                                st.push(make_pair(temp_i*N+temp_j,gone));
                                if ((temp_j==0)||(forbidden.count(temp_i*N+temp_j-1)==1)||(board[temp_i][temp_j-1]!=word[forbidden.size()]))
                                    continue;
                                forbidden.insert(temp_i*N+temp_j-1);
                                st.push(make_pair(temp_i*N+temp_j-1,up));
                            }
                            if (dir==gone)
                            {
                                st.pop();
                                forbidden.erase(temp_i*N+temp_j);
                            }
                        }
                    }
                }
            return false;
        }
    };
    

    Then I switch from the unordered_set to a 2-D bool array for availability checking, hope that extra space can buy me some time. However, it got TLE this time on the case ["aaa...aa",...,"aaa...ab"], "aa...ab".
    Can some one tell me what makes my two codes inefficient? thanks!
    I don't think there is problem in correctness, since it is modified from my AC code.

    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            // This part is the same as version one
            stack<pair<int,int> > st;
            bool **Used = new bool*[M];
            for (int i=0; i<M; i++)
                Used[i] = new bool [N];
            for (int i=0; i<M; i++)
                for (int j=0; j<N; j++)
                {
                    if (board[i][j]==word[0])
                    {
                        if (L==1)
                            return true;
                        st.push(make_pair(i*N+j,up));
                        Used[i][j] = true;
                        l = 1;
                        while (!st.empty())
                        {
                            if (l==L)
                                return true;
                            temp_i = st.top().first; dir = st.top().second;
                            temp_j = temp_i%N; temp_i /= N;
                            if (dir==up)  // to check up
                            {
                                st.pop();
                                st.push(make_pair(temp_i*N+temp_j,right));
                                if ((temp_i==0)||(Used[temp_i-1][temp_j])||(board[temp_i-1][temp_j]!=word[l]))
                                    continue;
                                Used[temp_i-1][temp_j] = true;
                                l++;
                                st.push(make_pair((temp_i-1)*N+temp_j,up));
                                continue;
                            }
                           // EACH POST HAS 8000 CHAR LIMIT, SO THE RIGHT TO LEFT PART IS OMITTED HERE
                            if (dir==gone)
                            {
                                st.pop();
                                Used[temp_i][temp_j] = false;
                                l--;
                            }
                        }
                    }
                }
            for (int i=0; i<M; i++)
                delete [] Used[i];
            delete [] Used;
            return false;
        }
    };

  • 0
    J

    You can use board to record which cell is traversed, restore it's value if need backtrace.
    This will save program's running time.


Log in to reply
 

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