Dynamic programming 17.2, variant 3. Minimum number of of characters to remove to make string palindrome

#1

Hi,

There is couple of explanations for similar problems on the web which I don’t buy. I would like to know is this is the correct way of doing that.

My initial cache looks like this:
0, 1, 2, 3, 4,<- those values denotes the number of characters needed to deleted to make it empty string, the same 1 col
1, 0, 0, 0, 0,
2, 0, 0, 0, 0,
3, 0, 0, 0, 0,
4, 0, 0, 0, 0,

I’m trying to solve this using Lev distance modified algorithm, in which I don’t care about modifying characters i.e:

void getLevenstein(std::string const& current, std::string const& currReversed, std::vector<std::vector<int>>& cache) {

    for (int i = 1; i <= current.size(); ++i) {
        for (int j = 1; j <= current.size(); ++j) {
            if (current[i-1] == currReversed[j-1]) {
                cache[i][j] = cache[i-1][j-1];
            } else {
                cache[i][j] = 1 + std::min({cache[i-1][j], cache[i][j-1]});
            }
        }
    }
}

My idea is simple, I count number of deletes for string to make it reverse of itself. So basically i try to find a min pivot in cache array after computation that is minimum, by going diagonal. For input with even number of characters it should be in the diagonal path as number of characters has to be the same from front and back of the string in palindrome, for example for word “even” resulting cache looks like this:

0, 1, 2, 3, 4,
1, 2, 1, 2, 3,
2, 3, 2, 1, 2,
3, 4, 3, 2, 1,
4, 3, 4, 3, 2,

Minimum is 2.

But for word with odd number of characters, diagonal path is not enough we should also check upper and lower entries, as palindrome cannot be perfectly sliced to half.
So for word “odd” resulting cache looks like this:

0, 1, 2, 3,
1, 2, 3, 2,
2, 1, 2, 3,
3, 2, 1, 2,

And min is 1

Is that correct way of doing that or I should take some other approach?

Thanks,

0 Likes
#2

To decide if it is correct please pose these 3 questions to yourself:

(1) Does it pass a comprehensive set of tests, including (and especially) corner cases?
(2) Does the form of the solution fit what is considered dynamic programming (i.e. bottom-up, non-recursive, and cached solutions to sub-problems)?
(3) Is its time and space complexity the best that can be achieved for a dynamic programming solution?

If you can answer yes to all, you’re done. In that case the only difference between your answer and some other correct one will be somewhat superficial characteristics as clarity, conciseness, etc.

If you answer yes to only some, then you know exactly where you either need to do more exploration, or seek guidance.

0 Likes
#3

Hmm,

(1) Does it pass a comprehensive set of tests, including (and especially) corner cases? - its not :confused:
It was working for some simple cases but it is not, when I tried to test it with more examples.

I noticed that my idea is fine but I’m making wrong assumption about how to read the result. I think I just cannot traverse cache from top left to bottom right. More reasonable would be to go from bottom left to top right(or top right to bottom left). This means take the whole string and tell me what is te minimum number of modifications to make the string and its reverse equal. I think that the key point here is that as we go up and check up or down values in cache it denotes deletes!
This modified version works well.

(2) Does the form of the solution fit what is considered dynamic programming (i.e. bottom-up, non-recursive, and cached solutions to sub-problems)? - yes

(3) Is its time and space complexity the best that can be achieved for a dynamic programming solution? - yes its O(n*n)

Thanks

0 Likes
#4

Cool. Sounds like you were able to come up with answers to your question.

0 Likes