I need to be able to discern if a string of an arbitrary length, greater than 1 (and only lowercase), has the same set of characters within a base or template string.
For example, take the string "aabc": "azbc" and "aaabc" would be false while "acba" would be true.
Is there a fast way to do this in python without keeping track of all the permutations of the first string and then comparing it to the test string?
6 Answers
Sort the two strings and then compare them:
sorted(str1) == sorted(str2)
If the strings might not be the same length, you might want to make sure of that first to save time:
len(str1) == len(str2) and sorted(str1) == sorted(str2)
This is the O(n) solution
from collections import Counter
Counter(str1) == Counter(str2)
But the O(n * log n) solution using sorted is likely faster for sensible values of n
Here's a variation on @Joowani's solution that only uses one dictionary and runs even faster (at least on my machine) :
def cmp4(str1, str2):
if len(str1) != len(str2):
return False
d = collections.defaultdict(int)
for c in str1:
d[c] += 1
for c in str2:
d[c] -= 1
return all(v == 0 for v in d.itervalues())
Here is another O(n) solution, longer but slightly faster than others:
def cmp(str1, str2):
if len(str1) != len(str2):
return False
d, d2 = {}, {}
for char in str1:
if char not in d:
d[char] = 1
else:
d[char] += 1
for char in str2:
if char not in d:
return False
if char not in d2:
d2[char] = 1
else:
d2[char] += 1
return d == d2
It basically does the same thing as gnibber's solution (but for some strange reasons the Counter() from collections library seems quite slow). Here are some timeit results:
setup = '''
import collections
from collections import Counter
s1 = "abcdefghijklmnopqrstuvwxyz" * 10000
s2 = s1[::-1]
def cmp1(str1, str2):
if len(str1) != len(str2):
return False
d, d2 = {}, {}
for char in str1:
if char not in d:
d[char] = 1
else:
d[char] += 1
for char in str2:
if char not in d:
return False
if char not in d2:
d2[char] = 1
else:
d2[char] += 1
return d == d2
def cmp2(str1, str2):
return len(str1) == len(str2) and sorted(str1) == sorted(str2)
def cmp3(str1, str2):
return Counter(str1) == Counter(str2)
def cmp4(str1, str2):
if len(str1) != len(str2):
return False
d = collections.defaultdict(int)
for c in str1:
d[c] += 1
for c in str2:
d[c] -= 1
return all(v == 0 for v in d.itervalues())
'''
timeit.timeit("cmp1(s1, s2)", setup=setup, number = 100)
8.027034027221656
timeit.timeit("cmp2(s1, s2)", setup=setup, number = 100)
8.175071701324946
timeit.timeit("cmp3(s1, s2)", setup=setup, number = 100)
14.243422195893174
timeit.timeit("cmp4(s1, s2)", setup=setup, number = 100)
5.0937542822775015
Also, David's solution comes out on top when the string sizes are small and they actually have same characters.
EDIT: updated the test results
If you have a very long string, the following solution will be helpful with O(n) time complexity. You can also use an hash map/dictionary instead of the arrays/lists.
s1 = "sjkhdfkaljdhfaldflflad"
s2 = "lsdhfuisfslffsdjdkllja"
if len(s1)!=len(s2):
return False
ds1 = [0] * 26
ds2 = [0] * 26
for i in range(len(s1)):
ds1[ord(s1[i])-ord("a")] +=1
ds2[ord(s2[i])-ord("a")] +=1
return ds1 == ds2
Heres a different way. By using what we ignore the most "sets":
if len(set(str1) - set(str2)) == 0:
print "Yes"
