Saturday, 8 February 2014

Finding minimum window containing given subsequence

Question : 

It was long description for a DNA problem. Main DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPat). You have to find the minimum length window in strDNA where strPat is subsequence. (GeeksForGeeks)

Code : 

package Miscellaneous;

/**
 * Created by Aniket on 2/8/14.
 */
public class SmallestCommonSubSequenceFinder {

    String strDna;
    String strPat;


    char[] patternArray;
    char[] dnaArray;


    int bestLength;
    int bestStart;
    int bestEnd;

    public int getBestEnd() {
        return bestEnd;
    }

    public void setBestEnd(int bestEnd) {
        this.bestEnd = bestEnd;
    }

    public int getBestStart() {
        return bestStart;
    }

    public void setBestStart(int bestStart) {
        this.bestStart = bestStart;
    }

    public int getBestLength() {
        return bestLength;
    }

    public void setBestLength(int bestLength) {
        this.bestLength = bestLength;
    }


    public SmallestCommonSubSequenceFinder(String strDna, String strPat){
        this.strDna = strDna;
        this.strPat = strPat;
        this.patternArray = strPat.toCharArray();
        this.dnaArray = strDna.toCharArray();
    }

    public int getStartIndex(int start){
        for(int i=start;i<dnaArray.length;i++){
            if(dnaArray[i] == patternArray[0]){
                return i;
            }
        }
        return -1;
    }

    public void findMinSubSeqDNAWindow(int start,int currIndex, int comparingIndex, boolean isStart){

        if(start >= dnaArray.length || currIndex >= dnaArray.length){
            return;
        }

        while(currIndex < dnaArray.length && dnaArray[currIndex] != patternArray[comparingIndex]){
            currIndex++;
        }

        //check if currIndex has exceeded the array length

        if(currIndex >= dnaArray.length){
            //element not found
            return;
        }

        if(isStart){
            start = currIndex;
            isStart = false;
        }

        if(comparingIndex == patternArray.length-1){
            int lengthOfSubSeq = currIndex - start + 1;
            if(bestLength == 0 || lengthOfSubSeq < bestLength){
                bestLength = lengthOfSubSeq;
                bestStart = start;
                bestEnd = currIndex;
            }
            //start finding new sub sequence
            findMinSubSeqDNAWindow(start + 1, start + 1, 0, true);
        }
        else {
            //go for next character
            findMinSubSeqDNAWindow(start, currIndex+1, comparingIndex+1, isStart);
        }
    }

    public static void main(String args[]){
        String strPat = "bdf";
        String strDna = "abcdefgbdf";

        SmallestCommonSubSequenceFinder finder = new SmallestCommonSubSequenceFinder(strDna,strPat);
        finder.findMinSubSeqDNAWindow(0,0,0,true);
        System.out.println("Best Length : " + finder.getBestLength());
        System.out.println("BestStart : " + finder.getBestStart());
        System.out.println("Best End : " + finder.getBestEnd());
    }
}



Output :

Best Length : 3
BestStart : 7
Best End : 9
t> UA-39527780-1 back to top