progress

~/problems / Arrays & hashing / Python toolkit

Index words by line with defaultdict

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~10 min

A book's index lists, for each word, the pages it appears on. Build one for a short text.

Write word_index(lines: list[str]) -> dict[str, list[int]] that maps every word to the numbers of the lines it appears on.

  • Lines are numbered from 1.
  • Words are separated by any amount of whitespace (spaces or tabs, possibly at the start or end of a line).
  • Words are compared ignoring case and stored in lower case: "The" and "the" are the same word.
  • Each word's list is in increasing order and holds each line number once, even if the word appears several times on that line.
word_index(["the cat sat", "The  dog", "cat cat nap"])
# {"the": [1, 2], "cat": [1, 3], "sat": [1], "dog": [2], "nap": [3]}

word_index(["", "   "])   # {}
  • 0 <= len(lines) <= 10^4, each line has at most 200 characters, and lines hold only letters, spaces and tabs.
  • The order of the keys doesn't matter, and returning the defaultdict itself is fine.
Show hint

collections.defaultdict(list) creates an empty list the first time you touch a key. Split with line.split() (no argument): split(" ") turns every extra space into an empty "word".

Topic: Python toolkit. Counter, deque, heapq, bisect, itertools: the standard library to know cold, and its traps.

0:00
Ctrl ' run · Ctrl ↵ submit
esc