CODEWITHSUNDEEP
pythonalgorithmrecursion
Jeffrey Lee
Jeffrey Lee

Reputation: 51

How do I count the occurrence of a given string in list that has more nested lists/dictionaries?

During a technical phone screen, I was given a list similar to below and asked to count the number of times the string 'a' occurs:

input = ['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]]

As you can see, in addition to the 'a' being an item in the list, it can also be an item in nested lists, as well as the keys and/or values in nested dictionaries.

This is the code I have so far in Python:

def count_letter_a(arr):

    count = 0

    for item in arr:
        if item == 'a':
            count += 1
        elif isinstance(item, list):
            count_letter_a(item)
        elif isinstance(item, dict):
            for k, v in item.items():
                pass

    return count

I'm stuck on what to do with the handling of dictionary keys/values portion of my function. What do I need to do?

Upvotes: 0

Views: 183

Answers (2)

user2390182
user2390182

Reputation: 73470

You can just add the 'a' count of keys and values, or simple recursively apply it to the items directly. This requires that you count occurrences in tuples as well (I included sets to complete the built-in collections):

def count_a(obj):
    if isinstance(obj, (list, tuple, set)):
        return sum(map(count_a, obj))
    if isinstance(obj, dict):
        return sum(map(count_a, obj.items()))
    if obj == 'a':
        return 1
    return 0

>>> x = ['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]]
>>> count_a(x)
7

Upvotes: 4

Mulan
Mulan

Reputation: 135287

You're really close!

def count (x):
  if isinstance (x, list):
    return sum (count (y) for y in x)
  elif isinstance (x, dict):
    return sum (count ([ k, v ]) for k,v in x.items ())
  elif x == "a":
    return 1
  else:
    return 0

It works like this

count ('foo')
# 0

count ([ 'a', 'b', 'c' ])
# 1

count (['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]])
# 7

Upvotes: 3

Related Questions