Java Easy Iterative solution using dfs


#1
public class Solution {
    class Pair{
        int x,y,count;
        Pair(int x,int y,int count){
            this.x=x;
            this.y=y;
            this.count=count;
        }
    }
    int shiftX[] = new int[]{-1,0,0,1};
    int shiftY[] = new int[]{0,-1,1,0};
    boolean isValid(int i,int j,int count,int row,int col,ArrayList<String> list, String word){
        if(i>=0 && i<row && j>=0 && j<col && count <= word.length() && list.get(i).charAt(j)==word.charAt(count-1))
        return true;
        return false;
    }
    boolean callDfs(int i,int j,int row,int col,ArrayList<String> list, String word){
        Stack<Pair> stack = new Stack();
        stack.push(new Pair(i,j,1));
        while(!stack.isEmpty()){
            Pair p = stack.pop();
            int x = p.x,y=p.y,count=p.count;
            if(count==word.length()){
                return true;
            }
            for(int k=0;k<4;k++){
                int nx = x+shiftX[k];
                int ny = y+shiftY[k];
                if(isValid(nx,ny,count+1,row,col,list,word)){
                    stack.push(new Pair(nx,ny,count+1));
            }
            }
        }
        return false;
    }
    public int exist(ArrayList<String> list, String word) {
        if(list.size()==0) return 0;
        int row=list.size();
        int col= list.get(0).length();
        for(int i=0;i<row;i++){
            for(int j=0;j<list.get(i).length();j++){
                if(list.get(i).charAt(j)==word.charAt(0)){
                    if(callDfs(i,j,row,col,list,word)){
                        return 1;
                    }
            }
        }
    }
    return 0;
  }
}