Time Limit Exceeded Last executed input: ["aaaa","aaaa","aaaa","aaaa","aaab"], "aaaaaaaaaaaaaaaaaaaa"


  • 0
    Y

    My code works in local, but not in OJ. My idea is simply do a DFS for every qualified entry and return true if find a valid path. I use hashset to record visited nodes. Below is the code. Thanks

     public class Solution {
        public class pos{
            int i;
            int j;
            public pos(int _i,int _j){
                i=_i;
                j=_j;
            }
            public int hashCode(){
            	return 197*i+37*j;
            }
            public boolean equals(Object p1){
            	pos p2 = (pos) p1;
            	if(i==p2.i&&j==p2.j)return true;
            	return false;
            }
        }
        
        public boolean DFS(char[][] board, int i, int j, String word, HashSet<pos> set){
            //break condition
            if(word==null || word.length()==0) return true;
            //check if position<i,j> is out of boundary 
            if(i<0||i>=board.length||j<0||j>=board[0].length) return false;
            //check if the character in current position<i,j> equals to the first character in word
            if(board[i][j] != word.charAt(0)) return false;
            //create a new set object with all previous visited nodes
            HashSet<pos> newSet = new HashSet<pos>(set);
            //check if <i,j> is visited or not
            if(newSet.add(new pos(i,j))){
                //remove first character from word, recursively check four adjacency directions
            	String s = word.substring(1);
            	return DFS(board,i+1,j,s,newSet) || DFS(board,i-1,j,s,newSet) || DFS(board,i,j-1,s,newSet) || DFS(board,i,j+1,s,newSet);    
            }
            return false;
        }
        public boolean exist(char[][] board, String word) {
            if(board==null)return false;
            if(word==null) return true;
            //if word length bigger than board size, simply return false
            if(word.length()>board.length*board[0].length)return false;
            //traverse board, return true when find a valid path
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if(DFS(board,i,j,word, new HashSet<pos>())) return true;
                }
            }
            return false;
        }
    }

  • 0
    S

    Could you please update your post with the correct code format? Select all code, then click {} button. And also, add comment in your code. Thanks.


  • 0
    Y

    I've updated my post per your request. Thank you for your time!


  • 7
    S

    I am not familiar with Java, but I think you are wasting large time on new a set object, i.e. this statement HashSet<pos> newSet = new HashSet<pos>(set);.

    So I try to change part of your code from

        //create a new set object with all previous visited nodes
        HashSet<pos> newSet = new HashSet<pos>(set);
        //check if <i,j> is visited or not
        if(newSet.add(new pos(i,j))){
            //remove first character from word, recursively check four adjacency directions
            String s = word.substring(1);
            return DFS(board,i+1,j,s,newSet) || DFS(board,i-1,j,s,newSet) || DFS(board,i,j-1,s,newSet) || DFS(board,i,j+1,s,newSet);    
        }
    

    to

        pos now = new pos(i,j);
        //check if <i,j> is visited or not
        if(set.add(now)){
            //remove first character from word, recursively check four adjacency directions
            String s = word.substring(1);
            if (DFS(board,i+1,j,s,set) || DFS(board,i-1,j,s,set) || DFS(board,i,j-1,s,set) || DFS(board,i,j+1,s,set)) {
                return true;
            }
            set.remove(now);
        }
    

    Then, it passed.

    However, I do not think it is necessary to create a pos object to do the hash set check. All you need is a 2d matrix, boolean mark[board.size][board[0].size].


  • 0
    Y

    Thanks for your suggestion, 2d matrix does make things easier. I should've thought of that first. Appreciate your help!


Log in to reply
 

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