a = "hello"
b = "olhel"
print sorted(a) == sorted(b)
Glenn Maynard
2010-09-30 00:26:23
wow, thanks! I cant believe i didn't find that in google.
Jack S.
2010-09-30 00:29:57
in a simple example, like yours, it works flawlessly. but in my hangman game, it does the same thing (I printed the strings to check that they are equal) it doesent work. Could you please tell me whats wrong? code:http://dl.dropbox.com/u/10141934/hangman.py (line 230)
Jack S.
2010-09-30 01:05:19
You'll have to debug for yourself. Print out the sorted values and see how they're inequal. Case? Whitespace? Different length?
Glenn Maynard
2010-09-30 01:08:40
+4
A:
An O(n) algorithm is to create a dictionary of counts of each letter and then compare the dictionaries.
In Python 2.7 or newer this can be done using collections.Counter:
>>> from collections import Counter
>>> Counter('hello') == Counter('olhel')
True
Mark Byers
2010-09-30 00:31:39
@Rafe with another example of the meaninglessness of the buzzword "Pythonic".
Glenn Maynard
2010-09-30 00:41:38
It certainly has no meaning where you just used it. What were you trying to say? "In a Python-specific manner" is hardly a positive trait. There's nothing seriously wrong with this solution (at a glance, anyway), but it's in no way more natural as Python code than mine.
Glenn Maynard
2010-09-30 00:54:41
@Mark: I think this is O(m log n), where m is the length of the string and n is the number of distinct letters. You're iterating over every letter (m), then finding the letter in the underlying dict of n entries. In practice, since dict is a hash table, it'll probably perform close to O(n) for smaller values of n, but if you throw lots of distinct characters at it (eg. CJK) it'll probably degrade significantly.
Glenn Maynard
2010-09-30 01:03:38
@Glenn: I suppose I see what you mean, but I don't think complementing someone for using Python to its fullest is a bad thing.
Rafe Kettler
2010-09-30 01:50:48
@Glenn: where does the log n come from? n is bounded by a small constant, hence updating ocurrences of letters should be O(1).
Sheldon L. Cooper
2010-09-30 04:20:18
@Sheldon: n isn't inherently bounded, and may be large for some languages. Of course, the OP is probably just solving word scrambles for CS102, where it wouldn't matter if it was O(n^2).
Glenn Maynard
2010-09-30 05:45:54