I know no one ever replies to these, but I'm about to tear my hair out. This test passes on my computer, fails on the Online Judge. No static variables used


  • 0
    T
    public class Solution {
    	public boolean exist(char[][] board, String word)
    	{
    		if (word.length() == 0)
    			return true;
    
    		if (board.length == 0 || board[0].length == 0)
    			return false;
    		
    		for (int i = 0; i < board.length; ++i)
    		{
    			for (int j = 0; j < board[0].length; ++j)
    			{
    				HashSet<Point> visited = new HashSet<Point>();
    				if (DFS(board, visited, i, j, word, 0))
    					return true;
    			}
    		}
    
    		return false;
    	}
    
    	private boolean withinBounds(char[][] board, int i, int j)
    	{
    		return i >= 0 && i < board.length && j >= 0 && j < board[0].length;
    	}
    
    	private boolean DFS(char[][] board, HashSet<Point> visited, int i, int j, String word, int curPos)
    	{
    		if (curPos == word.length())
    			return true;
    		
    		if (!withinBounds(board, i, j))
    			return false;
    		
    		if (word.charAt(curPos) != board[i][j])
    			return false;
    
    		Point currentPoint = new Point(i, j);
    		visited.add(currentPoint);
    		boolean result = false;
    		
    		int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    		
    		for (int[] dir : dirs)
    		{
    			int newX = i + dir[0];
    			int newY = j + dir[1];
    			if (!visited.contains(new Point(newX, newY)))
    			{
    				result |= DFS(board, visited, newX, newY, word, curPos + 1); 
    			}
    		}
    
    		visited.remove(currentPoint);
    
    		return result;
    	}
    }
    

    The test that fails is ["aa"], word is aaa. My computer outputs false, but the OJ says my solution outputs true.


Log in to reply
 

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