## 732 - Anagrams by Stack

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 732 - Anagrams by Stack

can anyone help me?

I'm getting always RTE

Code: Select all

``````#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef vector<int> VI;

void process(string sw, string tw, VI &slet, string stack, string seq, int a, int b)
{
if (b == tw.size())
{
seq = seq.substr(1);
cout << seq << endl;
}
else
{
if (slet[tw[b] - 'a'] > 0)
{
slet[sw[a] - 'a']--;
process(sw, tw, slet, stack + sw[a], seq + " i", a + 1, b);
slet[sw[a] - 'a']++;
}
int stam = stack.size();
if (stam > 0 and stack[stam - 1] == tw[b])
process(sw, tw, slet, stack.substr(0, stam - 1), seq + " o", a, b + 1);
}
}

int main()
{
string sw, tw;
while (cin >> sw >> tw)
{
cout << '[' << endl;
if (sw.size() == tw.size())
{
VI slet(26, 0), tlet(26, 0);
for (int i = 0; i < sw.size(); i++) slet[sw[i] - 'a']++;
for (int i = 0; i < tw.size(); i++) tlet[tw[i] - 'a']++;
bool valid = true;
for (int i = 0; i < 26 and valid; i++)
valid = valid and (slet[i] == tlet[i]);
if (valid) process(sw, tw, slet, "", "", 0, 0);
}
cout << ']' << endl;
}
}
``````
I don't know in witch case it can crash...

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

### Re: 732 - Anagrams by Stack

This is one where the UDebug output differs from AC judge output.
The UDebug solution ignores empty lines entirely; you can't do that - if you do, you'll WA

Input:

Code: Select all

``````d_g
g_d

f

f
aaaabbb
ababaab
``````
UDebug Output:

Code: Select all

``````[
i i i o o o
]
[
i o
]
[
i i i i o i o o i o o o i o
i i i o i i o o i o o o i o
i i o i i i o o i o o o i o
i o i i i i o o i o o o i o
]
``````
AC output:

Code: Select all

``````[
i i i o o o
]
[
]
[
]
[
i i i i o i o o i o o o i o
i i i o i i o o i o o o i o
i i o i i i o o i o o o i o
i o i i i i o o i o o o i o
]
``````
It took me a long time to figure this out, so please use this information!!

RedGreenCode
New poster
Posts: 7
Joined: Wed May 13, 2015 3:41 am
Location: Seattle, WA, USA
Contact:

### Re: 732 - Anagrams by Stack

I wrote an editorial about optimizing a Java solution to this problem to get it to run in under the time limit: http://www.redgreencode.com/implementin ... o-uva-732/
Deliberate practice techniques for software developers -- http://www.redgreencode.com/