CODEWITHSUNDEEP
stringalgorithmdynamic-programming
user3188300
user3188300

Reputation: 431

Find number of distinct paths by which a string can be derived

There is a secret message that is a string of length at least 2 containing only the characters A..Z.

Apply a sequence of "operations" to it. An Operation is shown in the example.

Given the final encrypted string, count the number of possible ways you could have produced this string using one or more repeated operations applied to a source string. Operations are distinct even if they give the same encryption of your secret message. I.E. : There are four distinct separate ways to obtain AAA from AA.

Here is an example:

The encrypted string is: ABABA. The output would be: 8. Here are the different ways you could have produced ABABA:

  1. Start with AB -> AB+A -> AB+ABA
  2. Start with AB -> AB+A -> ABA+BA 3.Start with ABA -> AB+ABA
  3. Start with ABA -> ABA+BA
  4. Start with BA -> A+BA -> AB+ABA
  5. Start with BA -> A+BA -> ABA+BA
  6. Start with ABAB -> ABAB+A
  7. Start with BABA -> A+BABA

Could you please help suggest an algorithm to solve this. I thought of trying recursion but on bigger inputs my code runs way to slow.

Upvotes: 2

Views: 136

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Not sure if this is correct, but here's a recursive attempt in JavaScript:

function f(str){
    var total = 0

    function g(ptr,len){
        for (var i=1; i<= (len%2 == 0 ? len/2 - 1: (len - 1)/2); i++){
            var left = str.substr(ptr,len - i),
                suffix = str.substr(ptr + len - i,i),
                right = str.substr(ptr + i,len - i),
                prefix = str.substr(ptr,i),
                recurseL = false,
                recurseR = false

            if (suffix == left.substr(-i)){
                total++
                recurseL = true
            }
            if (suffix == left.substr(0,i)){
                total++
                recurseL = true
            }
            if (prefix == right.substr(-i)){
                total++
                recurseR = true
            }
            if (prefix == right.substr(0,i)){
                total++
                recurseR = true
            }

            if (recurseR)
                g(ptr + i,len - i)
            if (recurseL)
                g(ptr,len - i)
        }
        return total
    }

    return g(0,str.length)
}

f("ABABA")

Output:

8

Upvotes: 0

tmyklebu
tmyklebu

Reputation: 14205

Notice that, at each step of your derivation, you wind up with a substring of the "encrypted" string. There are quadratically many (i.e. O(n^2)) such substrings.

You can find the number of ways to derive the final string from each of its suffixes and prefixes straightforwardly.

So, you have quadratically many possible subproblems, and you can break a problem down into a complete set of subproblems, do the counting on each subproblem, and add the results up.

You get a dynamic programming algorithm out of this by solving each subproblem only once. This dynamic programming algorithm can be made to run in cubic time.

Upvotes: 2

Related Questions