Set permutations creative solution for The End of Other by nickie - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Set permutations solution in Creative category for The End of Other by nickie

from itertools import permutations
checkio = lambda s: any(1 for a, b in permutations(s, 2) if a.endswith(b))

Feb. 20, 2014

Comments:

nickie on Feb. 20, 2014, 5:05 p.m.
When I find some time, I'll publish a solution that will do this efficiently. This one is O(N^2*K), ignoring the unnecessary overhead of sets (say the parameter s was an array instead), where N is the number of words and K is the maximum word length. Can you do this in O(N*K)? More specifically, can you do this and traverse each word at most once?

veky on Feb. 20, 2014, 7:06 p.m.
Do you assume the number of possible characters is O(1)?

nickie on Feb. 20, 2014, 7:19 p.m.
Well, I suppose yes, after all they will be strings in Python. If they are not, I'll allow an extra O(logN)... :-)

veky on Feb. 20, 2014, 7:23 p.m.
Unicode could potentially be infinite, you know... :-)

james.verran on July 7, 2014, 9:43 a.m.
OK, I tried to do a single traverse. (But there is sort and endswith takes a tuple.) Thoughts? <a href="http://www.checkio.org/mission/end-of-other/publications/james.verran/python-27/strmp-endswith-tuple/">http://www.checkio.org/mission/end-of-other/publications/james.verran/python-27/strmp-endswith-tuple/</a>

Different kind of sets

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!