Does this question needs Hamilton Path or Euler Path. In my opinion it needs Hamilton Path but then how can we solve this ???
Were you able to solve this? I am trying to solve it with euler path but it is always giving ‘wa’! Can you help?
I think that while this may be solved using a Hamiltonian Path solver, this doesn’t necessarily need one.
In other words, you can reduce this problem to Hamiltonian Path, but you cannot reduce Hamiltonian Path to this problem (clearly: for any general graph, it may not be possible to find words of length <= 1000 from only 26 letters, which induce the same graph).
For another example:
Graph colorability is a “difficult” problem.
Consider the problem of being given N time intervals in which there are meetings, and you need to find the minimum number of rooms to conduct those meetings such that they do not overlap.
This can obviously be solved using graph colorability - however, there is also a very simple greedy solution for it.
In general, try to prove that an NP-Hard problem reduces to a given problem, before declaring it impossible.
Eulerian is the right approach.
@darkshv22: Either you are not working on the right graph or you didn’t check all conditions for an Eulerian path.
Euler path. The words are edges and you need to take each of them exactly once; think, what are the vertices?
Also, watch out for multiple edges.