UVa 732

From Algorithmist

Contents 1 732 - Anagrams by stack 2 Summary 3 Explanation 4 Gotcha's 5 My Way 6 Input 7 Output

[edit] 732 - Anagrams by stack

• http://acm.uva.es/p/v7/732.html

[edit] Summary

Anagrams - by switching first word's letter's position get another word.

[edit] Explanation

You get pairs of words, and you have to find out, how many ways there is to get from the first to the seconds using stack and stack only.

[edit] Gotcha's

Be as effective as possible, or else you'll end up TLE.

[edit] My Way

Use recursive programming. Start with first word and call push method on first letter. Then each step (push and pop) performs itself, checks for end conditions (no more letters, invalid stack operation,...) and calls both push and pop on the rest of the word.

Example: ok -> ko  
push - push - push invalid
            - pop - push invalid
                  - pop OK, print output
     - pop invalid

[edit] Input

madam
adamm
bahama
bahama
long
short
eric
rice

[edit] Output

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

Recursive Programming