Help with DFS problem

Question: Crackers
Basically the question is to say if a string s can be converted to another string t with given mappings. I made a directed graph, did dfs, then checked if the distance to all the characters of t were reached. If any remained, then outputted “YES”. However, I am getting WA despite passing all the test cases. -
My submission: 34899961
What am I doing wrong here?

You can’t maintain a global visited array for processing all characters. You have to run a dfs for every i and check if there is a path from s[i] to t[i] in your graph.

Take this mapping.
s = aa
t = vq
a->v

While processing the second ‘a’ you will skip it, because it is visited. But in the graph there is no path from ‘a’ to ‘q’.

1 Like

tbh, its so hard to understand your code.

Won’t that be slow. Might as well use dp then.
Thank you.

It will definitely slower than dp, but it’s fast enough to pass the limits. There are just 26 vertices in your grraph. So each dfs is O(26 + 650), which is not that slow. So the overall complexity will be O(676n).

1 Like

they have written in statement of input section that string lengths need NOT be equal??

how can be convert a string into another of different length with just single character mappings?

We can’t. So if s.size() != t.size() we just print “NO”,

Btw, I’ve been debugging this for a while, and I can’t seem to find the error in my dfs. Can you take a look? Submission.

I’m checking if the destination string characters have been reached, not the source.
s = aa
t = vq
a->v

Then v will be reached and q won’t be. My code is giving the correct answer.

Well, my bad. Check this.

s = abb
t = xyq
3
a->x
a->q
b->y

It’s important you understand why your code would fail here. There can be multiple components in the graph.

I think there’s something wrong with dfs method, So I changed it a bit, and I have added a condition when s[i] == t[i], now its AC. submission

1 Like

Thanks! But were you able to figure out what was going wrong in the bool dfs() version? It looked pretty solid to me…

I couldn’t figure out what was wrong…

1 Like

you would have to take full input before saying NO for unequal length of strings.

i tried it still WA.

Yes another issue was that, I was not clearing the adjacency list (when I print “NO” and immediately return). I moved that to the top. And s != t after taking input, and AC. Thanks!

1 Like