DP Solution with Matrix (JAVA), easy to understand


  • 0
    Y
    public int numDistinct(String s, String t) {
    	int lengthS=s.length();
    	int lengthT=t.length();
    	if(lengthS<lengthT)
    		return 0;
    	if(lengthT==0)
    		return 1;
    
    			
        int[][] matrix=new int[lengthT+1][lengthS+1];
        for(int i=0;i<=lengthS;i++)
        	matrix[0][i]=0;
        for(int i=0;i<=lengthT;i++)
        	matrix[i][0]=0;
        for(int col=1;col<=lengthS;col++){
        	if(t.charAt(0)==s.charAt(col-1)){
        		matrix[1][col]=matrix[1][col-1]+1;
        	}
        	else{
        		matrix[1][col]=matrix[1][col-1];
        	}
        }
        for(int row=2;row<=lengthT;row++){
        	for(int col=1;col<=lengthS;col++){
        		if(t.charAt(row-1)==s.charAt(col-1)){
        			matrix[row][col]=matrix[row-1][col-1]+matrix[row][col-1];
        		}
        		else
        			matrix[row][col]=matrix[row][col-1];
        	}
        }
        return matrix[lengthT][lengthS];
    }

Log in to reply
 

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