blocks|key|1447733|text|我认为第一个是“显而易见”的方式。它更短、更清晰，而且在许多情况下可能会更快，因为Python的内置排序已经过了高度优化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1447734|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I think the first one is the "obvious" way. It is shorter, clearer, and likely to be faster in many cases because Python's built-in sort is highly optimized.

blocks|key|1662574|text|这里有一种方法是O(n)，比你建议的两种方法渐近更好。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1662575|import+collections

def+same_permutation(a,+b):
++++d+=+collections.defaultdict(int)
++++for+x+in+a:
++++++++d[x]+%2B=+1
++++for+x+in+b:
++++++++d[x]+-=+1
++++return+not+any(d.itervalues())

##+same_permutation([1,2,3],[2,3,1])
#.+True

##+same_permutation([1,2,3],[2,3,1,1])
#.+False|code-block|syntax|javascript|1662576|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is a way which is O(n), asymptotically better than the two ways you suggest. 

<pre><code>import collections

def same_permutation(a, b):
 d = collections.defaultdict(int)
 for x in a:
 d[x] += 1
 for x in b:
 d[x] -= 1
 return not any(d.itervalues())

## same_permutation([1,2,3],[2,3,1])
#. True

## same_permutation([1,2,3],[2,3,1,1])
#. False
</code></pre>

blocks|key|1447872|text|使用第一个--它更直接，也更容易理解。如果您实际上正在处理非常大的字符串，并且性能是一个真正的问题，那么不要使用Python，而应该使用类似C的语言。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1447873|就Python的禅宗而言，应该只有一种明显的方法来做事情，这指的是小而简单的事情。显然，对于任何足够复杂的任务，总会有无数种小的变化来完成它。|1447874|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Go with the first one - it's much more straightforward and easier to understand. If you're actually dealing with incredibly large strings and performance is a real issue, then don't use Python, use something like C.

As far as the Zen of Python is concerned, that there should only be one obvious way to do things refers to small, simple things. Obviously for any sufficiently complicated task, there will always be zillions of small variations on ways to do it.

blocks|key|1447934|text|下面是一些使用两种不同方法对非常小的字符串执行的定时操作：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1447935|排序计数(特别是@namin的原始方法)。|1447936|a,+b,+c+=+'confused',+'unfocused',+'foncused'

sort_method+=+lambda+x,y:+sorted(x)+==+sorted(y)

def+count_method(a,+b):
++++d+=+{}
++++for+x+in+a:
++++++++d[x]+=+d.get(x,+0)+%2B+1
++++for+x+in+b:
++++++++d[x]+=+d.get(x,+0)+-+1
++++for+v+in+d.itervalues():
++++++++if+v+!=+0:
++++++++++++return+False
++++return+True|code-block|syntax|javascript|1447937|这两个方法超过100,000次循环的平均运行时间是：|1447938|不匹配(字符串a和b)|1447939|$+python+-m+timeit+-s+'import+temp'+'temp.sort_method(temp.a,+temp.b)'
100000+loops,+best+of+3:+9.72+usec+per+loop
$+python+-m+timeit+-s+'import+temp'+'temp.count_method(temp.a,+temp.b)'
10000+loops,+best+of+3:+28.1+usec+per+loop|1447940|匹配(字符串a和c)|1447941|$+python+-m+timeit+-s+'import+temp'+'temp.sort_method(temp.a,+temp.c)'
100000+loops,+best+of+3:+9.47+usec+per+loop
$+python+-m+timeit+-s+'import+temp'+'temp.count_method(temp.a,+temp.c)'
100000+loops,+best+of+3:+24.6+usec+per+loop|1447942|请记住，使用的字符串非常小。这些方法的时间复杂度是不同的，因此对于非常大的字符串，您将看到不同的结果。根据你的数据进行选择，你甚至可以使用两者的组合。|1447943|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|10|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|11|8|@]|9|@]|A|$G|H]]|$1|O|3|P|5|6|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|13|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

Here are some timed executions on very small strings, using two different methods: 
1. sorting 
2. counting (specifically the original method by @namin).

<pre><code>a, b, c = 'confused', 'unfocused', 'foncused'

sort_method = lambda x,y: sorted(x) == sorted(y)

def count_method(a, b):
 d = {}
 for x in a:
 d[x] = d.get(x, 0) + 1
 for x in b:
 d[x] = d.get(x, 0) - 1
 for v in d.itervalues():
 if v != 0:
 return False
 return True
</code></pre>

Average run times of the 2 methods over 100,000 loops are:

non-match (string a and b)

<pre><code>$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.b)'
100000 loops, best of 3: 9.72 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.b)'
10000 loops, best of 3: 28.1 usec per loop
</code></pre>

match (string a and c)

<pre><code>$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.c)'
100000 loops, best of 3: 9.47 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.c)'
100000 loops, best of 3: 24.6 usec per loop
</code></pre>

Keep in mind that the strings used are very small. The time complexity of the methods are different, so you'll see different results with very large strings. Choose according to your data, you may even use a combination of the two.

blocks|key|1662796|text|启发式地，您可能更好地根据字符串大小将它们分开。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1662797|伪码：|1662798|returnvalue+=+false
if+len(a)+==+len(b)
+++if+len(a)+<+threshold
++++++returnvalue+=+(sorted(a)+==+sorted(b))
+++else
+++++++returnvalue+=+naminsmethod(a,+b)
return+returnvalue|code-block|syntax|javascript|1662799|如果性能很重要，字符串的大小可以很大也可以很小，那么我就会这么做。|1662800|根据输入大小或类型来拆分这样的东西是很常见的。算法有不同的优点或缺点，使用一种算法会更好，这将是愚蠢的……在这种情况下，Namin的方法是O(+n)，但具有比O(n+log+N)排序方法更大的常数因子。|1662801|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

heuristically you're probably better to split them off based on string size.

Pseudocode:

<pre><code>returnvalue = false
if len(a) == len(b)
 if len(a) &lt; threshold
 returnvalue = (sorted(a) == sorted(b))
 else
 returnvalue = naminsmethod(a, b)
return returnvalue
</code></pre>

If performance is critical, and string size can be large or small then this is what I'd do.

It's pretty common to split things like this based on input size or type. Algorithms have different strengths or weaknesses and it would be foolish to use one where another would be better... In this case Namin's method is O(n), but has a larger constant factor than the O(n log n) sorted method.

blocks|key|1662858|text|这个版本比到目前为止提供的任何示例都要快，除了对于短字符串它比sorted(x)+==+sorted(y)慢20%25。这取决于用例，但通常情况下，20%25的性能提升不足以证明通过对短字符串和长字符串使用不同的版本来证明代码的复杂性是合理的(就像@patros的答案一样)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1662859|它不使用len，所以它接受任何迭代值，因此它甚至可以处理内存中不能容纳的数据，例如，给定两个有许多重复行的大文本文件，它会回答这两个文件是否有相同的行(行可以是任何顺序)。|1662860|def+isanagram(iterable1,+iterable2):
++++d+=+{}
++++get+=+d.get
++++for+c+in+iterable1:
++++++++d[c]+=+get(c,+0)+%2B+1
++++try:
++++++++for+c+in+iterable2:
++++++++++++d[c]+-=+1
++++++++return+not+any(d.itervalues())
++++except+KeyError:
++++++++return+False|code-block|syntax|javascript|1662861|目前还不清楚为什么这个版本比defaultdict+(@namin's)更快，一个适用于大型iterable1的版本(在25MB同义词库上测试)。|1662862|如果我们将循环中的get替换为try:+...+except+KeyError，那么对于短字符串，即当重复项很少时，它的执行速度会慢2倍。|1662863|entityMap^0|V|M|0|4|3|0|0|E|B|1A|9|0|9|3|F|O|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|V|8|@$9|W|A|X|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|Y|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|Z|8|@$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@]|E|$]]|$1|O|3|P|5|6|7|14|8|@$9|15|A|16|B|C]|$9|17|A|18|B|C]]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|19|8|@]|D|@]|E|$]]]|R|$]]

This version is faster than any examples presented so far except it is 20% slower than <code>sorted(x) == sorted(y)</code> for short strings. It depends on use cases but generally 20% performance gain is insufficient to justify a complication of the code by using different version for short and long strings (as in @patros's answer).

It doesn't use <code>len</code> so it accepts any iterable therefore it works even for data that do not fit in memory e.g., given two big text files with many repeated lines it answers whether the files have the same lines (lines can be in any order).

<pre><code>def isanagram(iterable1, iterable2):
 d = {}
 get = d.get
 for c in iterable1:
 d[c] = get(c, 0) + 1
 try:
 for c in iterable2:
 d[c] -= 1
 return not any(d.itervalues())
 except KeyError:
 return False
</code></pre>

It is unclear why this version is faster then <code>defaultdict</code> (@namin's) one for large <code>iterable1</code> (tested on 25MB thesaurus).

If we replace <code>get</code> in the loop by <code>try: ... except KeyError</code> then it performs 2 times slower for short strings i.e. when there are few duplicates.

blocks|key|1662927|text|很抱歉，我的代码不是用Python编写的，我从来没有用过它，但我相信这可以很容易地翻译成python。我相信这比已经发布的所有其他示例都要快。它也是O(n)，但会尽快停止：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1662928|public+boolean+isPermutation(String+a,+String+b)+{
++++if+(a.length()+!=+b.length())+{
++++++++return+false;
++++}

++++int[]+charCount+=+new+int[256];
++++for+(int+i+=+0;+i+<+a.length();+%2B%2Bi)+{
++++++++%2B%2BcharCount[a.charAt(i)];
++++}

++++for+(int+i+=+0;+i+<+b.length();+%2B%2Bi)+{
++++++++if+(--charCount[b.charAt(i)]+<+0)+{
++++++++++++return+false;
++++++++}
++++}
++++return+true;
}|code-block|syntax|javascript|1662929|首先，我不使用字典，而是使用大小为256的数组来存储所有字符。访问索引应该要快得多。然后，当迭代第二个字符串时，当计数低于0时，我立即返回false。当第二个循环结束时，您可以确定字符串是一个排列，因为字符串具有相同的长度，并且与a相比，b中没有使用更频繁的字符。|1662930|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Sorry that my code is not in Python, I have never used it, but I am sure this can be easily translated into python. I believe this is faster than all the other examples already posted. It is also O(n), but stops as soon as possible:

<pre><code>public boolean isPermutation(String a, String b) {
 if (a.length() != b.length()) {
 return false;
 }

 int[] charCount = new int[256];
 for (int i = 0; i &lt; a.length(); ++i) {
 ++charCount[a.charAt(i)];
 }

 for (int i = 0; i &lt; b.length(); ++i) {
 if (--charCount[b.charAt(i)] &lt; 0) {
 return false;
 }
 }
 return true;
}
</code></pre>

First I don't use a dictionary but an array of size 256 for all the characters. Accessing the index should be much faster. Then when the second string is iterated, I immediately return false when the count gets below 0. When the second loop has finished, you can be sure that the strings are a permutation, because the strings have equal length and no character was used more often in b compared to a.

blocks|key|1448164|text|这是python中的martinus代码。它只适用于ascii字符串：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1448165|def+is_permutation(a,+b):
++++if+len(a)+!=+len(b):
++++++++return+False

++++char_count+=+[0]+*+256
++++for+c+in+a:
++++++++char_count[ord(c)]+%2B=+1

++++for+c+in+b:
++++++++char_count[ord(c)]+-=+1
++++++++if+char_count[ord(c)]+<+0:
++++++++++++return+False

++++return+True|code-block|syntax|javascript|1448166|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here's martinus code in python. It only works for ascii strings:

<pre><code>def is_permutation(a, b):
 if len(a) != len(b):
 return False

 char_count = [0] * 256
 for c in a:
 char_count[ord(c)] += 1

 for c in b:
 char_count[ord(c)] -= 1
 if char_count[ord(c)] &lt; 0:
 return False

 return True
</code></pre>

blocks|key|1448212|text|我用Java和我在一本书中的所有单词做了一个相当彻底的比较。计数方法在各个方面都优于排序方法。结果：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1448213|Testing+against+9227+words.

Permutation+testing+by+sorting+...+done.++++++++18.582+s
Permutation+testing+by+counting+...+done.+++++++14.949+s|code-block|syntax|javascript|1448214|如果任何人想要算法和测试数据集，请注释掉。|1448215|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I did a pretty thorough comparison in Java with all words in a book I had. The counting method beats the sorting method in every way. The results:

<pre><code>Testing against 9227 words.

Permutation testing by sorting ... done. 18.582 s
Permutation testing by counting ... done. 14.949 s
</code></pre>

If anyone wants the algorithm and test data set, comment away.

blocks|key|1663066|text|在Python3.1/2.7中，你可以只使用collections.Counter(a)+==+collections.Counter(b)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1663067|但sorted(a)+==+sorted(b)仍然是最明显的IMHO。您正在谈论的是排列-改变顺序-所以排序是消除这种差异的明显操作。|1663068|entityMap^0|M|1C|0|1|M|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|P|8|@]|D|@]|E|$]]]|I|$]]

In Python 3.1/2.7 you can just use <code>collections.Counter(a) == collections.Counter(b)</code>.

But <code>sorted(a) == sorted(b)</code> is still the most obvious IMHO. You are talking about permutations - changing order - so sorting is the obvious operation to erase that difference.

blocks|key|1663099|text|这是从@patros'+answer派生的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1663100|from+collections+import+Counter

def+is_anagram(a,+b,+threshold=1000000):
++++"""Returns+true+if+one+sequence+is+a+permutation+of+the+other.

++++Ignores+whitespace+and+character+case.
++++Compares+sorted+sequences+if+the+length+is+below+the+threshold,
++++otherwise+compares+dictionaries+that+contain+the+frequency+of+the
++++elements.
++++"""
++++a,+b+=+a.strip().lower(),+b.strip().lower()
++++length_a,+length_b+=+len(a),+len(b)
++++if+length_a+!=+length_b:
++++++++return+False
++++if+length_a+<+threshold:
++++++++return+sorted(a)+==+sorted(b)
++++return+Counter(a)+==+Counter(b)++#+Or+use+@namin's+method+if+you+don't+want+to+create+two+dictionaries+and+don't+mind+the+extra+typing.|code-block|syntax|javascript|1663101|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/396570/72321^0|3|F|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

This is derived from <a href="https://stackoverflow.com/a/396570/72321">@patros' answer</a>.

<pre><code>from collections import Counter

def is_anagram(a, b, threshold=1000000):
 """Returns true if one sequence is a permutation of the other.

 Ignores whitespace and character case.
 Compares sorted sequences if the length is below the threshold,
 otherwise compares dictionaries that contain the frequency of the
 elements.
 """
 a, b = a.strip().lower(), b.strip().lower()
 length_a, length_b = len(a), len(b)
 if length_a != length_b:
 return False
 if length_a &lt; threshold:
 return sorted(a) == sorted(b)
 return Counter(a) == Counter(b) # Or use @namin's method if you don't want to create two dictionaries and don't mind the extra typing.
</code></pre>

blocks|key|1663151|text|在Swift+(或其他语言实现)中，您可以查看编码值(在本例中为Unicode)并查看它们是否匹配。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1663152|类似于：|1663153|let+string1EncodedValues+=+"Hello".unicodeScalars.map()+{
//each+encoded+value
$0
//Now+add+the+values
}.reduce(0){+total,+value+in
++++total+%2B+value.value
}

let+string2EncodedValues+=+"oellH".unicodeScalars.map()+{
++++$0
++++}.reduce(0)+{+total,+value+in
++++total+%2B+value.value
}

let+equalStrings+=+string1EncodedValues+==+string2EncodedValues+?+true+:+false|code-block|syntax|javascript|1663154|您需要根据需要处理空格和大小写。|1663155|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

In Swift (or another languages implementation), you could look at the encoded values ( in this case Unicode) and see if they match. 

Something like:

<pre><code>let string1EncodedValues = "Hello".unicodeScalars.map() {
//each encoded value
$0
//Now add the values
}.reduce(0){ total, value in
 total + value.value
}

let string2EncodedValues = "oellH".unicodeScalars.map() {
 $0
 }.reduce(0) { total, value in
 total + value.value
}

let equalStrings = string1EncodedValues == string2EncodedValues ? true : false
</code></pre>

You will need to handle spaces and cases as needed.

blocks|key|1448306|text|def+matchPermutation(s1,+s2):
++a+=+[]
++b+=+[]

++if+len(s1)+!=+len(s2):
++++print+'length+should+be+the+same'
++return

++for+i+in+range(len(s1)):
++++a.append(s1[i])

++for+i+in+range(len(s2)):
++++b.append(s2[i])

++if+set(a)+==+set(b):
++++print+'Permutation+of+each+other'
++else:
++++print+'Not+a+permutation+of+each+other'
++return

#matchPermutaion('rav',+'var')+#returns+True
matchPermutaion('rav',+'abc')+#returns+False|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1448307|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>def matchPermutation(s1, s2):
 a = []
 b = []

 if len(s1) != len(s2):
 print 'length should be the same'
 return

 for i in range(len(s1)):
 a.append(s1[i])

 for i in range(len(s2)):
 b.append(s2[i])

 if set(a) == set(b):
 print 'Permutation of each other'
 else:
 print 'Not a permutation of each other'
 return

#matchPermutaion('rav', 'var') #returns True
matchPermutaion('rav', 'abc') #returns False
</code></pre>

blocks|key|1448336|text|这是一个Python语言的O(n)解决方案，使用哈希和字典。请注意，我没有使用默认字典，因为如果我们在检查第二个字母后确定两个字符串不是排列，则代码可能会以这种方式停止。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1448337|def+if_two_words_are_permutations(s1,+s2):
++++if+len(s1)+!=+len(s2):
++++++++return+False
++++dic+=+{}
for+ch+in+s1:
++++if+ch+in+dic.keys():
++++++++dic[ch]+%2B=+1
++++else:
++++++++dic[ch]+=+1
for+ch+in+s2:
++++if+not+ch+in+dic.keys():
++++++++return+False
++++elif+dic[ch]+==+0:
++++++++return+False
++++else:
++++++++dic[ch]+-=+1
return+True|code-block|syntax|javascript|1448338|entityMap^0|D|4|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

This is an <code>O(n)</code> solution in Python using hashing with dictionaries. Notice that I don't use default dictionaries because the code can stop this way if we determine the two strings are not permutations after checking the second letter for instance.

<pre><code>def if_two_words_are_permutations(s1, s2):
 if len(s1) != len(s2):
 return False
 dic = {}
for ch in s1:
 if ch in dic.keys():
 dic[ch] += 1
 else:
 dic[ch] = 1
for ch in s2:
 if not ch in dic.keys():
 return False
 elif dic[ch] == 0:
 return False
 else:
 dic[ch] -= 1
return True
</code></pre>

blocks|key|1663210|text|在Python中检查两个字符串是否为彼此的排列|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1663211|#+First+method
def+permutation(s1,s2):
+if+len(s1)+!=+len(s2):return+False;
+return+'+'.join(sorted(s1))+==+'+'.join(sorted(s2))


#+second+method
def+permutation1(s1,s2):
+if+len(s1)+!=+len(s2):return+False;
+array+=+[0]*128;
+for+c+in+s1:
+array[ord(c)]+%2B=1
+for+c+in+s2:
+++array[ord(c)]+-=1
+++if+(array[ord(c)])+<+0:
+++++return+False
+return+True|code-block|syntax|javascript|1663212|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

<h1>Checking if two strings are permutations of each other in Python</h1>

<pre><code># First method
def permutation(s1,s2):
 if len(s1) != len(s2):return False;
 return ' '.join(sorted(s1)) == ' '.join(sorted(s2))


# second method
def permutation1(s1,s2):
 if len(s1) != len(s2):return False;
 array = [0]*128;
 for c in s1:
 array[ord(c)] +=1
 for c in s2:
 array[ord(c)] -=1
 if (array[ord(c)]) &lt; 0:
 return False
 return True
</code></pre>

blocks|key|1448373|text|首先，为了解决这样的问题，例如字符串1和字符串2是否完全相同，很容易，你可以使用一个"if“，因为它是O(1)。其次，重要的是要考虑它们是仅仅是数值，还是也可以是字符串中的单词。如果后一种情况为真(字符串中同时存在单词和数值)，则第一个解决方案将不起作用。您可以通过使用"ord()“函数来增强它，使其成为ASCII数值。但是，最终您将使用sort；因此，在最坏的情况下，您的时间复杂度将为O(NlogN)。这个时间复杂度还不错。但是，你可以做得更好。你可以把它设为O(N)。我的“建议”是同时使用Array(list)和set。注意，在数组中寻找一个值需要迭代，所以它的时间复杂度是O(N)，但是在集合中寻找一个值(我猜它是用Python语言中的HashTable实现的，我不确定)的时间复杂度是O(1)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1448374|def+Permutation2(Str1,+Str2):

ArrStr1+=+list(Str1)+#convert+Str1+to+array
SetStr2+=+set(Str2)+#convert+Str2+to+set

ArrExtra+=+[]

if+len(Str1)+!=+len(Str2):+#check+their+length
++++return+False

elif+Str1+==+Str2:+#check+their+values
++++return+True

for+x+in+xrange(len(ArrStr1)):
++++ArrExtra.append(ArrStr1[x])

for+x+in+xrange(len(ArrExtra)):+#of+course+len(ArrExtra)+==+len(ArrStr1)+==len(ArrStr2)
++++if+ArrExtra[x]+in+SetStr2:+#checking+in+set+is+O(1)
++++++++continue
++++else:
++++++++return+False

return+True|code-block|syntax|javascript|1448375|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

First, for solving such problems, e.g. whether String 1 and String 2 are exactly the same or not, easily, you can use an "if" since it is O(1).
Second, it is important to consider that whether they are only numerical values or they can be also words in the string. If the latter one is true (words and numerical values are in the string at the same time), your first solution will not work. You can enhance it by using "ord()" function to make it ASCII numerical value. However, in the end, you are using sort; therefore, in the worst case your time complexity will be O(NlogN). This time complexity is not bad. But, you can do better. You can make it O(N).
My "suggestion" is using Array(list) and set at the same time. Note that finding a value in Array needs iteration so it's time complexity is O(N), but searching a value in set (which I guess it is implemented with HashTable in Python, I'm not sure) has O(1) time complexity:

<pre><code>def Permutation2(Str1, Str2):

ArrStr1 = list(Str1) #convert Str1 to array
SetStr2 = set(Str2) #convert Str2 to set

ArrExtra = []

if len(Str1) != len(Str2): #check their length
 return False

elif Str1 == Str2: #check their values
 return True

for x in xrange(len(ArrStr1)):
 ArrExtra.append(ArrStr1[x])

for x in xrange(len(ArrExtra)): #of course len(ArrExtra) == len(ArrStr1) ==len(ArrStr2)
 if ArrExtra[x] in SetStr2: #checking in set is O(1)
 continue
 else:
 return False

return True
</code></pre>

blocks|key|1448382|text|def+permute(str1,str2):
++++if+sorted(str1)+==+sorted(str2):
++++++++return+True
++++else:
++++++++return+False

str1="hello"
str2='olehl'
a=permute(str1,str2)
print(a|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1448383|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>def permute(str1,str2):
 if sorted(str1) == sorted(str2):
 return True
 else:
 return False

str1="hello"
str2='olehl'
a=permute(str1,str2)
print(a
</code></pre>

blocks|key|1448385|text|from+collections+import+defaultdict
def+permutation(s1,s2):
++++h+=+defaultdict(int)
++++for+ch+in+s1:
++++++++h[ch]%2B=1
++++for+ch+in+s2:
++++++++h[ch]-=1
++++for+key+in+h.keys():
++++++++if+h[key]!=0+or+len(s1)!=+len(s2):
++++++++++++return+False
++++++++return+True
print(permutation("tictac","tactic"))|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1448386|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>from collections import defaultdict
def permutation(s1,s2):
 h = defaultdict(int)
 for ch in s1:
 h[ch]+=1
 for ch in s2:
 h[ch]-=1
 for key in h.keys():
 if h[key]!=0 or len(s1)!= len(s2):
 return False
 return True
print(permutation(&quot;tictac&quot;,&quot;tactic&quot;))
</code></pre>

I'm checking if two strings <code>a</code> and <code>b</code> are permutations of each other, and I'm wondering what the ideal way to do this is in Python. From the Zen of Python, "There should be one -- and preferably only one -- obvious way to do it," but I see there are at least two ways:

<pre><code>sorted(a) == sorted(b)
</code></pre>

and

<pre><code>all(a.count(char) == b.count(char) for char in a)
</code></pre>

but the first one is slower when (for example) the first char of <code>a</code> is nowhere in <code>b</code>, and the second is slower when they are actually permutations.

Is there any better (either in the sense of more Pythonic, or in the sense of faster on average) way to do it? Or should I just choose from these two depending on which situation I expect to be most common?

Checking if two strings are permutations of each other in Python

Python

Swift

Java

我正在检查两个字符串a和b是否是彼此的排列，我想知道用Python语言做这件事的理想方法是什么。在Python的禅宗中，“应该有1个，最好只有一个--这是显而易见的方法”，但我认为至少有两种方法：sorted(a) == sorted(b)和all(a.count(char) == b.count(char) for ...

问在Python中检查两个字符串是否为彼此的排列
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python中检查两个字符串是否为彼此的排列EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python中检查两个字符串是否为彼此的排列
EN