선형 시간에 아나그램 문자열 확인

Question

두 문자열의 입력이 주어 지므로 한 문자열이 다른 문자열의 아나그램인지 확인하기 위해 다음 선형 시간 솔루션을 사용할 수 있습니다. 나는 이것에 더 간결하고 비단뱀적인 선형 시간 해결책을 원했다.

def perm_check(str1,str2): 

    if len(str1)!=len(str2): 
     return False 

    d1,d2={},{} 

    for i in range(len(str1)): 

     l1=str1[i] 
     l2=str2[i] 

     if l1 in d1: 
      d1[l1]+=1 
     else: 
      d1[l1]=1 


     if l2 in d2: 
      d2[l2]+=1 
     else: 
      d2[l2]=1 


    for letter in d1: 

     if letter not in d2: 
      return False 

     if d1[letter] != d2[letter]: 

      return False   

    return True 


print(perm_check("stab","bats")) 

어떻게 최적화 할 수 있습니까?

Answer 1

파이썬 collections.Counter 클래스를 사용하면이 작업을 수행 할 수 있습니다. 기본적으로, anagrams에서 각 문자의 수는 두 문자열 사이에서 동일해야하므로 두 문자열 모두에서 각 문자의 문자 수가 필요합니다. Counter 클래스는 직접 비교할 수있는 사전을 만듭니다.

from collections import Counter 

def is_anagram(string1, string2): 
    return Counter(string1) == Counter(string2) 

결과 : 요소를 통해 이동하고 모든 문자의 빈도를 계산하는 다른 대답, 또는 사전에 언급 한 바와 같이

>>> is_anagram("helper", "perhel") 
True 
>>> is_anagram("helper", "perhe") 
False 
>>> is_anagram("helper", "perhes") 
False 

Answer 2

당신은 어느 카운터를 사용할 수 있습니다.

zip을 사용하면 같은 위치에 요소를 가져 와서 두 개의 목록을 탐색 할 수 있습니다 (동일한 길이의 사물을 가속화하기 위해). 키가 존재하면 추가합니다. 존재하지 않는 경우, 우리는 값 1

def perm_check(str1,str2): 
    if len(str1)!=len(str2): 
     return False 

    d1,d2={},{} 

    for x,y in zip(list(str1),list(str2)): 
     if x not in d1.keys(): 
      d1[x]=1 
     else: 
      d1[x]+=1 

     if y not in d2.keys(): 
      d2[y]=1 
     else: 
      d2[y]+=1 


    return d1==d2 

print perm_check("dad","add") #True 

print perm_check("dad","adb") #False 

Answer 3

로, 사전에 키를 추가는 분류 사용 :

>>> def anagram(str1,str2): 
...  return sorted(str1) == sorted(str2) 
... 
>>> anagram('hello','ellho') 
True 
>>> anagram('abcd','cabd') 
True 
>>> anagram('hello','hellohe') 
False 

Answer 4

potential = ["ice", "cei", "cheese", "pool", "loop", "oolp", "eseehc"] 
sets = [] 
setCount = {} 
results = [] 
for anagram in potential: 
    sets.append((set(anagram), anagram)) 
for x in sets: 
    if not ''.join(list(x[0])) in setCount: 
     setCount[''.join(list(x[0]))] = [x[1]] 
    elif len(setCount[''.join(list(x[0]))][0]) == len(x[1]): 
     setCount[''.join(list(x[0]))].append(x[1]) 
     results += setCount[''.join(list(x[0]))] 
print(list(set(results)))