Find the number of occurrences of a subsequence in a string

user_810876 0
Viewed 29516

For example, let the string be the first 10 digits of pi, 3141592653, and the subsequence be 123. Note that the sequence occurs twice:

3141592653
 1    2  3
   1  2  3

This was an interview question that I couldn't answer and I can't think of an efficient algorithm and it's bugging me. I feel like it should be possible to do with a simple regex, but ones like 1.*2.*3 don't return every subsequence. My naive implementation in Python (count the 3's for each 2 after each 1) has been running for an hour and it's not done.

dynamic-programming algorithm python
9 Answers

A Javascript answer based on dynamic programming from geeksforgeeks.org and the answer from aioobe:

class SubseqCounter {
    constructor(subseq, seq) {
        this.seq = seq;
        this.subseq = subseq;
        this.tbl = Array(subseq.length + 1).fill().map(a => Array(seq.length + 1));
        for (var i = 1; i <= subseq.length; i++)
          this.tbl[i][0] = 0;
        for (var j = 0; j <= seq.length; j++)
          this.tbl[0][j] = 1;
    }
    countMatches() {
        for (var row = 1; row < this.tbl.length; row++)
            for (var col = 1; col < this.tbl[row].length; col++)
                 this.tbl[row][col] = this.countMatchesFor(row, col);

        return this.tbl[this.subseq.length][this.seq.length];
    }
    countMatchesFor(subseqDigitsLeft, seqDigitsLeft) {
            if (this.subseq.charAt(subseqDigitsLeft - 1) !=     this.seq.charAt(seqDigitsLeft - 1)) 
            return this.tbl[subseqDigitsLeft][seqDigitsLeft - 1];  
            else
            return this.tbl[subseqDigitsLeft][seqDigitsLeft - 1] +     this.tbl[subseqDigitsLeft - 1][seqDigitsLeft - 1]; 
    }
}
user_52171000
Related