Python dictionary sorting Anagram of a string

This question already has an answer here:

Permutation of string as substring of another 6 answers

---

A pure python solution for getting an object which corresponds to how many of that char in the alphabet is in a string (t)

Using the function chr() you can convert an int to its corresponding ascii value, so you can easily work from 97 to 123 and use chr() to get that value of the alphabet.

So if you have a string say:

t = "abracadabra"

then you can do a for-loop like:

dt = {}
for c in range(97, 123):
   dt[chr(c)] = t.count(chr(c))

this worked for this part of the solution giving back the result of:

{'k': 0, 'v': 0, 'a': 5, 'z': 0, 'n': 0, 't': 0, 'm': 0, 'q': 0, 'f': 0, 'x': 0, 'e': 0, 'r': 2, 'b': 2, 'i': 0, 'l': 0, 'h': 0, 'c': 1, 'u': 0, 'j': 0, 'p': 0, 's': 0, 'y': 0, 'o': 0, 'd': 1, 'w': 0, 'g': 0}

A different solution?

Comments are welcome, but why is storing in a dict necessary? using count() , can you not simply compare the counts for each char in t , to the count of that char in s ? If the count of that char in t is greater than in s return False else True .

Something along the lines of:

def question1(s, t):
   for c in range(97, 123):
      if t.count(chr(c)) > s.count(chr(c)):
         return False
   return True

which gives results:

>>> question1("udacity", "city")
True
>>> question1("udacity", "ud")
True
>>> question1("udacity", "ljljl")
False

If a dict is necessary...

If it is, then just create two as above and go through each key...

def question1(s, t):
   ds = {}
   dt = {}
   for c in range(97, 123):
      ds[chr(c)] = s.count(chr(c))
      dt[chr(c)] = t.count(chr(c))
   for c in range(97, 123):
      if dt[chr(c)] > ds[chr(c)]:
         return False
   return True

Update

The above answers ONLY CHECK FOR SUBSEQUENCES NOT SUBSTRING anagrams. As maraca explained to me in the comments, there is a distinction between the two and your example makes that clear.

Using the sliding window idea (by slicing the string), the code below should work for substrings :

def question1(s, t):
   dt = {}
   for c in range(97, 123):
      dt[chr(c)] = t.count(chr(c))
   for i in range(len(s) - len(t) + 1):
      contains = True
      for c in range(97, 123):
         if dt[chr(c)] > s[i:i+len(t)].count(chr(c)):
            contains = False
            break
      if contains:
         return True
   return False

The code above does work for ALL cases and utilizes a dictionary to speed up the calculations correctly :)

---

import collections
print collections.Counter("google")

Counter({'o': 2, 'g': 2, 'e': 1, 'l': 1})

链接地址: http://www.djcxy.com/p/40070.html

上一篇: 有没有O（1 / n）算法？

下一篇: Python字典排序字符串的Anagram