UVa 732

From Algorithmist
Jump to navigation Jump to search

732 - Anagrams by stack[edit]

Summary[edit]

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

Explanation[edit]

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.

Gotcha's[edit]

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

My Way[edit]

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

Input[edit]

madam
adamm
bahama
bahama
long
short
eric
rice

Output[edit]

[
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