2 ms·
> Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. My thought here is that you start from the outs
by im3w1l 6y ago
> Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
My thought here is that you start from the outside working inwards. When you encounter a conflict you must decide whether to resolve it by deleting the left or right character. Trying both possibilities should be good enough. From that decision point you just keep comparing and if it fails that branch failed.
- Stratoscope 6y agoYup, that is pretty much the solution I discussed with the interviewer after writing the code above. We ran out of time to write out the full code, but hopefully coming up with the rough description of a solution like yours was satisfactory. Waiting with bated breath for the interview feedback... :-)
- giu 6y agoIMHO you did very well if you were able to write down the correct naive solution and then discuss optimizations afterwards. Hopefully it works out for you! :) Godspeed!
- AstralStorm 6y agoThat's a quadratic solution. Try solving an inverse problem to get insight - how to know if a sequence is almost a palindrome and what's the "palindromicity" metric - and you will find the faster solutions. (I think it leads directly to a Knuth-Morris-Pratt like algorithm. And you can further apply a variant of divide and conquer on top.)
- im3w1l 6y agoNo it's not quadratic: since there is at most one conflict it will be linear.
- andi999 6y agoIt depends how you count. Is string reversion an O(1) or O(N) operation with N the string length? I believe is is O(N) and if you loop over it N times thats O(N^2), isnt it?
- im3w1l 6y agoI didn't want to post code, but I guess it's the only way I can see to settle the debate. This should be manifestly linear. def check(s): is_palindrome = lambda s: s == s[::-1] if is_palindrome(s): return True d = [a==b for a, b in zip(s, s[::-1])].index(False) return is_palindrome(s[d+1:len(s)-d]) or is_palindrome(s[d:-d-1]) edit: It must be len(s)-d rather than -d, to handle d=0.
- Someone 6y agoI’m not sure it is quadratic, but the “deleting the left or right character” to me, hint it deviates from linear. I think the solution, logically, is to cut the string in two halves, duplicating the center character for odd-length strings (¿or can you ignore it a bit more?), computing edit distance between the front half and the reversed right half, allowing only deletions, and bailing out as soon as you know the answer is larger than one. In real life, optimize away the “cut into two halves” and “reverse” parts, as they will be expensive.