Develop an algorithm which would determine whether the given input string is a palindrome or not. However there are certain constraints on the algorithm. The constraints are as follows -
- We do not know the length of the input string.
- We can read each character of the input string only once (I think the implication of this constraint along with the previous one should be clear).
- We have to employ constant space.
This problem is very interesting because its solution employs concepts which every computer engineer must have studied but very few will be able to connect the problem with it.
If we look carefully at the above constraints, we will recognize that they together specify a Deterministic Finite Automata. In other words, we are asked to recognize whether a string is palindrome or not through a DFA. This is clearly not possible.
Lets see how each constraint maps the required automaton to a DFA. (1) is just given to disallow quirks. (2) ensures that you cannot move back and forth on the input tape. This is again a characteristic of DFA where you scan symbols on input tape only once. (3) is again a characteristic of DFA, we should have finite states.
Hope you enjoyed the problem.
2 comments:
Isn't palindrome not a regular language and hence cannot be accepted by DFA ?
Perfect reasoning, the catch in the question was to figure out precisely this that the specification describes a DFA.
Post a Comment