anagram_substring.py

import copy

# fun from Ernest!
#
# Given two strings s and t, determine whether some anagram of t is a substring of s.
# For example: if s = "udacity" and t = "ad", then the function returns True.
# Your function definition should look like: question1(s, t) and return a boolean True or False.


# approach by orion.
# thanks to steve for pointing out error in backing up.
# i think this is no longer O(Ns) because we back-up by O(Nt).
def q_orion(s, t):
  # look thru s for the start of a possible anagram
  looking_good = 0

  # turn t into a map where the key is the letter and the value is the number of occurrences
  t_map = {}
  for c in t:
    if not c in t_map:
      t_map[c] = 0
    t_map[c] += 1

  working_map = copy.deepcopy(t_map)

  n = 0
  while n < len(s):
    c = s[n]
    if c in working_map:
      looking_good += 1
      working_map[c] -= 1
      if working_map[c] == 0:
        del working_map[c]

      if len(working_map) == 0:
        return True
    else:
      if looking_good > 0:
        working_map = copy.deepcopy(t_map)
        n -= looking_good
      looking_good = 0
    n += 1

  return len(working_map) == 0

from collections import Counter

# approach by steve
def q_steve(s,t):
    # create frequency count (O(N))
    tCount = Counter(t)
    for i in range(len(s)-len(t)+1):
        if (Counter(s[i:i+len(t)]) == tCount):
            return True
    return False

examples = [
  ['udacity', 'ad'     ],
  ['udacity', 'adi'    ],
  ['udacity', 'ytic'   ],
  ['udacity', 'ytc'    ],
  ['udacity', 'udacity'],
  ['udacity', 'cityuda'],
  ['blep'   , 'ee'     ],
  ['bleeper', 'ee'     ],
  ['bleeper', 'eee'    ],
  ['bleeper', 'eeep'   ],
  ['eep'    , 'ep'     ],
  ['abcadef','bcad'    ],
]

for ex in examples:
  s = ex[0]
  t = ex[1]
  print("o %20s in %20s ? %s" % (t, s, q_orion(s, t)))
  print("s %20s in %20s ? %s" % (t, s, q_steve(s, t)))

 # output
 #########################################
 #      ad in              udacity ? True
 #     adi in              udacity ? False
 #    ytic in              udacity ? True
 #     ytc in              udacity ? False
 # udacity in              udacity ? True
 # cityuda in              udacity ? True
 #      ee in                 blep ? False
 #      ee in              bleeper ? True
 #     eee in              bleeper ? False
 #    eeep in              bleeper ? True
 #      ep in                  eep ? True